I'm looking for a PC game that challenges the brain somewhat. Portal was good (although quite an exception in the brain challenging/entertaining bracket I assume), but any other games out there that require some real working of the grey matter?
Personal favourite by a long way: Deadly Rooms Of Death. Truly a devious puzzle game. No real-time action of any sort, but it'll make your brain hurt.
To get started for free, you can grab the demo of The City Beneath and the original King Dugan's Dungeon hold -- that's the level set from the original release, but in the newer engine. The demo will also play any of the 300-odd user-made holds here. Use the Change Location menu option to import them.
If you like it enough to spend money, the full Journey To Rooted Hold game is a better starting point in terms of learning curve. KDD is earlier in story terms, but pulls a few tricks which have since fallen out of favour with players. The full The City Beneath game is really designed for people with a bit of playing experience.
Probably getting a bit ahead here, but also note that if you end up getting the commercial version of King Dugan's Dungeon (2.0) later, the game considers it a different hold to the free download (it has voice acting, a handful of extra secret rooms, a proper ending and stuff). Unfortunately that means you can't transfer your progress from the free one to the commercial one.