1. Remove all the stuff that dumbs gameplay down - map markers, quest compasses, NPCs with quest markers above their heads, journals that tell you EXACTLY what to do in small steps.
2. Replace the stuff in step 1 with intelligent gameplay - NPCs giving intelligent directions based on landmarks, spatial navigation, quests being high level goals instead of detailed instructions of what to do.
For example, instead of typical braindead RPG go here, kill/bring X quests, how about something like: "Go to province Y, and overthrow the government there." That's it, no more instructions, details spelled out. You go there, and you figure out how to achieve this very high level goal by talking to NPCs, learning the culture, history of the place, the political relationships, the enmities between local factions, and then based on your newly acquired knowledge, create a plan utilizing your character skills to achieve the desired high level goal.