my team

I would get a Hoothoot. They fare well against the first few gym leaders and they're available in the beginning of the game. They also have great movepools, and are able to learn Roost early (you get TM 51, Roost, from winning at the first gym).
As for a grass-type, I wouldn't count on finding anything too great quickly. There aren't very many good grass-types to use, so you might as well not even consider them. If you can, though, trade one in from your other DS games; you can trade with Sinnoh right away in these games. However, if I were you, I wouldn't use a grass-type at least until you beat the Rockets. They appear often and always have at least one poison-type on them. Grass-types don't do well against...well, every Johto gym, to be honest...with the exception of Whitney [normal] and Chuck [fighting], but that's not much. Don't even worry about grass-types for now. Actually, if you really want a strong team, I suggest getting 2100 coins at the Game Corner in Goldenrod and exchanging them for a Dratini. Very good against the trainers in Johto.

I recommend either Dodrio or Fearow. Noctowl is also a good option. The pre-evolution forms for these Pokemon are Doduo, Spearow and Hoothoot, respectively.

I've always found Grass types to fare quite poorly in the Johto games. I'd recommend a Fighting type (as you mentioned as an alternative), and Machamp is still the champ of Fighting types.

Do not use a grass type, or at least use an electric type to counter the grass-ice weakness. Since you have Ampharos you already have that covered.

I'd suggest Lugia since it's a strong legendary, but that's just me.

You could always go to the pal park in diamond, pearl or platinum and lets say sceptile or venasur got imported from either fire-red or leaf-green or ruby sapphire or emerald. Since you can trade Pokemon from sinnoh into heart gold or soul silver straight away thats 1 option. For flying types you could maybe catch a hoothoot or pidgey quite early on and train that up or spearow butterfree and ledian are also other options but at the end of the day it's your game not mine so you make the decision I will have some more options tomorrow.