Solving a rubix cube (especially the first time) is fairly intense, and the process is a great mental workout.
My own suggestions are as follows (though many of them have already been addressed):
Learn a musical instrument: music is a global process in the brain, stimulating both the left (mathematical/analytical) and right (creative) hemispheres of the brain. Playing music requires precision, psycho-motor training, and creativity, all of which require you to be using your brain pretty hardcore.
Exercise: As important to when you're brain is working hard is when it gets a chance to shut down for a time. I find focusing on exercise for a good 45 minutes+ a couple of times a week clears my head. The physical strain of doing cardio and/or weight training is enough to force your brain to turn its concerns to the momentary task at hand, allowing your higher cognitive skills a bit of a break.
Get just enough sleep: I love to sleep, but if left to my own devices I'd sleep for 12-14 hours a day. I find getting up early in the morning regularly automatically makes me more productive throughout the day. Onc eyour body gets into a healthy rhythm of sleep and activity you can get the most out of your waking hours by not being tired all the time (either by not sleeping enough or sleeping too much - seriously, sleeping too much just makes you want to sleep more).
Read challenging works: Ever read Moby Dick? War and Peace? Ulysses? Try them out. Modernist literature (c1900-1945) in particular is great for a challenge since part of the philosophy of Modernist writers was to make books difficult to read so that only those deserving of their contents would ever get through them. Authors include Joyce, Beckett, Wolfe, Christie, and T.S. Eliot. Philosophy is great too, no matter the difficulty level for reading. Emmanuel Kant's stuff is challenging to read but worthwhile, or, if you'd prefer something a bit more directly readable but still very engaging, read Plato (great stuff). Or even just read in general, whatever you're into.
Play strategy games: Chess has already been suggested a lot, as has pokemon. What about Advance Wars? AW is a series of turn-based strategy games that has the player playing a military commander on one side of a battle. Playing through campaign mode can be challenging, but I really like creating my own maps with four different sides and trying to win each one with three CPU opponents. It forces you to adopt different strategies each time while trying to keep your plans fluid enough to roll with any surprises your opponent throws at you.
Table Top RPGs: One of my favorite games to play is a really interesting table top RPG that is run by a really good GM. Good GMs will force players to consistently think laterally to solve problems. Being forced to thikn laterally forces your brain to examine unconventional ways of doing things. MacGyver is a great example of a lateral thinker, or Parson Gotti from the erfworld webcomic (www.erfworld.com - which, btw, everyone should read). Aside from this aspect though, just the act of role playing - of putting yourself in someone else's shoes - is another advantage RPGing presents for developing your brain since it forces you to consider different perspectives.
Take a class: Sociology, psychology, english, math, engineering, chemistry, etc, etc. The point is learn something you didn't know before. If you are a good self-starter, don't even bother with the class, just pick up a text book and start plodding through it.
Write: either creatively or to make an argument. Just try to create something. Painting also falls under this heading too, whether it's just for fun or you want to make a statement. When you're done, ask people you know to critique what you've completed. For essays and serious works of art you should probably talk to someone like a teacher or professor to get academic feedback, but for creative works anyone with any eye or ear for your medium will do.
Hope that helps.
