I'm just on my second playthrough now. I'm trying to understand certain events by searching for everything I missed, and because it's such an engrossing world with wonderfully realised characters, I'm having as much fun as I did the first time.
I was very iffy about the game up until its release. I did wonder if it was just a cynical attempt at 'Bioshock in the Sky' in order to cash in, but it's so much more than that. I just wasn't expecting to get so involved in Elizabeth's plight.
If you're on the fence about this, it's certainly worth a punt.