Eh, I'm fine with him being where he is. Maybe make D-air and U-air end a bit faster, but I guess their slowness compensates for how strong of kill moves they are. I wouldn't mind D-air not making me bounce off of people's shields, and pogo-stick around so much. It's sooooooooooooooo unsafe on shields that I can't think about it without crying a little.
And, yeah, Link's got pleeeenty of recovery options. You've got the venerable Bomb Jump, the AGT+hookshot recovery (glide toss upwards, throw a bomb in whatever direction you see fit, air dodge towards the edge, clawshot), tether cancelling (not a method of recovery in itself, but enhances recovering through tether), and all that good stuff.