Thanks for all the recommendations guys! Thanks a lot, even if I don't mention them in this post. It is great indeed. So it seems Race for the Galaxy, Kingdom builder, Stone Age and Memoir 44 are all pretty popular. I am definitely considering them, and I think I will watch demo's for them because they sound like cool games.
I did watch a bit of a video on Race for the Galaxy, and it looks pretty complex. However I am sure it just takes time to learn it. How would it go in a situation where you are trying to teach friends at a games night?
Also I remember reading LastFootnote's article on the 'Donald X. Variety Mechanic', and realised that I really enjoy games with that too, and is one of the big reasons that I like Dominion so much. It certainly adds a lot of replay-ability, and interesting game set ups. Kingdom builder sounds like it has a lot of this, which makes sense since it was made by Donald X.
Android: Netrunner (although as I understand, this is a deckbuilder).
Netrunner is a Living Card Game (LCG), which for gameplay purposes is the same as being a TCG. So building decks is involved, but it's not incorporated into the game—you build your decks in advance and the game consists of playing them against each other. I haven't played my Netrunner yet, so can't recommend whether it's worth picking up. The core set is cheap.
Thanks for the clarification, that actually changes heaps. Just came back from a family holiday, and my uncle who is awesome, brought a MTG booster pack box of 36 packs so me and my brother and cousin could do a draft. We had a blast, and now I am really interested in CCG like that. So Android NetRunner might be perfect, since it plays like a TCG without actually having to collect heaps of good cards to make a good deck. Has anyone played it? Can anyone give me insight in how the game plays out, and how fun it is? I shall look up the thread on this too.
EDIT: Also the asymmetrical play of Netrunner intrigues me. Also a downside I can imagine with Netrunner is that it is quite difficult to teach new people, which I would have to do a lot of. How much harder is it to learn than say, Magic?