Assuming the class (with spells) is balanced, you should only give something new when something old is lost, not too much earlier. So I wouldn't give anything until 4th level, and I certainly wouldn't increase the HD.
I think some outdoorsy special/spell-like/supernatural abilities would be appropriate, for example at levels 4, 8, 12, 16, and 20. It could be as simple as giving spells as spell-like abilities (Commune with Nature?) or it could be new stuff.