XII is a game that definitely grew on me as well. My first play-through, I thought it was decent, but nothing spectacular. I played it again, this time using a guide so I got everything you could possibly find, and I was overwhelmed with how huge the game is.

For me, the side-quests didn't feel forced, they felt rather diverse and interesting. The mark hunting was great, and I wish you could repeat some of them!

The story, in and of itself, is fine. I mean, it wasn't exactly the greatest story ever, but it was perfectly acceptable. Where it fell down for me was the pacing. It was very hit and miss. After a strong start with Reks and the drama there, it then fell down slightly with Vaan and the rather mediocre opening with him. It picks up again when he invades the palace and with Balthier and Fran. But then again, it turns rather boring when you're traversing the Sandsea. In fact, I didn't really care for Jahara, or the Stilshrine of Miriam. After that, the rest of the story is probably paced well enough.