Those of you who keep your ATI drivers up-to-date might've noticed a new feature in CCC called "Morphological filtering" (in the 3D Application settings). It's a different form of AA that takes edges and blurs them together, adjusting the colors respectively. It's not true AA in the sense that it's more like a Photoshop filter. However this means that there's very little effect on performance, and that it'll work in every game, regardless of AA support.
I turned it on for GTA and noticed a definite improvement in edge smoothness (you might need to turn off the game's own filter by pressing P). It's not as good as true 4xAA, but I'd say it's comparable to 2x, and definitely a lot better than not having any sort of AA at all. I haven't measured FPS, but from just playing the game, I've noticed no significant drop in framerate.
I'm not sure if Nvidia users have this feature as well.
EDIT: The only downside I've noticed is that it screws up the text in Firefox 4 (since the browser is GPU-accelerated), so you might want to only use it when gaming, then turn it off to browse. Hopefully this'll be fixed in a later release.
Just note. The game engine used in GTA IV doesn't feature any anti-aliasing thus why you see those "weird" jaggy edges and black patched lines especially in daylight shadows and in character and vehicles models. Instead R* use their built-in feature of their proprietary engine to generate "AA-like" effects thus again why those weird jagged black edges in models. Why R* choose to do this is beyond me.
nVIDIA will soon have a WHQL supported version of this (SRAA), but actual support for games or performance is far from optimal at the moment. AMD's MLAA is also not without problems either, at the moment, but it appears they are ahead of nVIDIA shader based AA for now.
These techniques are supposed to be used as a lower cost AA technique in differential shaded rendered (or similar rendered) games.
@Zerol09 R* used a dynamic lighting system (I think it's called deferred lighting) that can't have AA in DX9, only DX10 and up. http://en.wikipedia.org/wiki/Deferred_lighting So if this game was built from the ground up for DX10, then R* wouldn't have to use post-processing effects and could use true AA. I'm not sure why "jaggies" are such a big concern to people. If you play on high resolution, you won't even notice them at all.