If you're talking about the original Vandal Hearts, I would say Vandal Hearts is significantly better. Here is a comparison of the games based on your criteria:
Story: FF9's is literally just FF7 and FF8, with pretty much the weaker elements of both. Really. Vandal Hearts has my favorite story out of any strategy game but Final Fantasy Tactics, and is actually fairly similar (they're both pretty strange).
Gameplay: FF9 has typical RPG gameplay. Very easy. With four player parties, slightly more strategy involved than the previous two Fantasies (although not really). Vandal Hearts has an interesting class system kind of like Shining Force's, but with a selection of two classes. With the number of characters and the completely different classes you can be (one class choice is very different, a spectacular monk or a magic dealing sorcerer. Another lets you be either a sniper or a winged swordsman (erm...k)), there are quite a few different possibilities for the team and variation for replay. Vandal Hearts is also fairly challenging, so if you don't choose your strategies and classes well, you'll really be hurting later on.
You didn't mention another category, but I'll say the music in FF9 is considerably better than Vandal Hearts.
Overall, if you don't care about the graphics, Vandal Hearts is the one I would suggest.
