Out of any projectiles, only Din's fire seems to me to be an issue (and possibly Pit's arrows), and even then only at high percentages. It will be more difficult, but not impossible, to deal with. You can cancel the attack with certain aerials, and you can jump out of the way, and you can fast fall to the ground, or fast fall below the ledge and do your jump and up-B recovery, and yes, you can still air dodge it. Zelda isn't the greatest character in the game anyway, and giving her more to do with Din's fire doesn't seem broken to me.
You don't land with any lag on the air dodge, not any more than simply jumping in the air without attacking causes, so your point about them waiting on the ground with a f-smash seems false.
As someone else once said, Brawl's AD system is part of the problem of Brawl. It makes the game more about defense than offense, and if removing it limits the defensive options in certain situations, so be it. You shouldn't be able to air dodge your way out of everything. Not only that, wavedashing opens up all kinds of movement possibilities for slow characters like Ike. I've played matches before where I literally spammed Ike's to death for the entire match with projectiles. You think this will be possible now that Ike's ground movement is 4x faster? No, the characters who are susceptible to spam now will be able to get around it much easier with the wavedash as a movement option.