WarioWare Touched and Elite Beat Agents are both tons of fun; they both kind of require you to look like a total idiot whilst playing them though.

Have you checked out Age of Empires: The Age of Kings? I loved that game, and it kicked my asssssssss. Some of the missions took me ages (pun intended) to complete.