I like some of the ideas on here and I think I may as well put an idea i've had that games just don't seem to have, but the post above kind of touches on. The Random Battles thing is a great idea and is classic rpg. I want to see quests focused around the possibility of Ambushes. Imagine this:

You go up to an NPC just outside the city and are given a very specific quest. A family is attempting to make its way from Ul'Dah to the ferry boats, but are fearful of potential attacks. Because of this, they ask for a party of bodyguards to escort the family (which would be in the form of a slow moving wagon pulled by a chocobo) along the road all the way to the destination. As you escort this wagon, you not only have to defend from the aggroing mobs already out on the map, but also quest specific party ambushes (I see it more of an ambush if theres no huge yellow circle on the map). These mob parties would have an actual strategic party, like a healer+dps+tank that your party has to adapt to in order to defeat. Your reward is based on how damaged the wagon is.

That's my crazy idea, and how fun would that be. =]