Since Blizzard did the world nerf back in The Burning Crusade, the single-player experience has sucked horribly. Much more recent changes to questing have certainly helped, but overall it's all way too easy.
It's so easy that people have to think up creative ways to make the game hard so that levelling a new character can be a challenge instead of a chore.
This is a mostly-unfinished concept. I did actually level characters with all of this in mind. However, since did need the characters asap I did wear BoAs.
- Hide the minimap, and no main map. This involves you in the world more.
- No flying. Again, this involves you in the world more. Taxis are ok, but don't be lazy.
No xp or reputation bars. This makes levelling a surprise.
Other stuff is feasible, like no use of the mailbox (no BoAs, no auction house, etc.)
A gathering concept:
- Allow yourself to constantly be distracted from questing by gathering nodes. Get off the path and follow the nodes. Get into trouble.
- Perhaps only level by gathering. You end up going after areas which are fairly challenging.
- Do your best to not aggro.
- If attacked while mounted, always flee.
- If attacked while dismounted, always fight.
Have patience for patrols.