MK almost certainly has the most options for recovering, since all four of his specials can be used for vertical and horizontal distance. They are also all damaging, which can deter less skillful edgeguarders. His multiple jumps are obviously a bonus. The only downsides I can see are his low air speed and the fact that his specials all send him into helpless.
Sonic also has a good recovery with his side- and neutral-specials, plus his Spring doesn't add the helpless state.
Samus is extremely difficult to kill; her heaviness guards against low-percentage kills and her floatiness gives her plenty of time to recover horizontally. Bomb-jumping gives her huge horizontal mobility without the need for a midair jump, and her Screw Attack/grapple beam give her several options for vertical recovery.
On the other end, Ivysaur has undeniably the worst recovery in the game. Olimar only needs about 4 of his pikmin to equal the reach of Ivysaur's vine, his midair jump is higher, and IIRC he has a faster horizontal air speed. If Ivysaur is off the ledge without his jump, he is assured to die against a player with any sense of how to edgehog.
EDIT: Also, Luigi. His air speed is awful, but he falls very slowly and has three of his four special moves to give him recovery. Tornado can be used directly after a midair jump for vertical and horizontal distance, the Missile is a obviously a good horizontal pusher, and the Jump Punch is his vertical option.