I've never really had a problem with legendary abilities or indeed feats, as long as they were used sensibly and didn't dominate the game. if you look at the Irish/Celtic myth cycle their heroes could do all sorts of weird stuff. One of them ( Cuchulainn ? ) did this thing where he'd cast 5 javelins at the enemy, jump up onto the javelins , run across them , leap down, strike down an enemy with his sword....and all before the first javelin struck.
You simply can't do that kind of thing with skill rolls alone, and that it seems to me is where legendary abilities come in. Equally consider the whole Wuxia genre, think of Crouching Tiger, Hidden Dragon and that sort of flying/running thing they do during the combat sequences. It could be some kind of spell, but it seems more like an innate ability of the characters themselves, once again I would say that that is what legendary abilities is all about.
Lastly, even RQ2 and 3 had something vaguely similiar in that various cults ( Humakt and I think Yelm ) had cult gifts and geasa.