You're eventually going to have to take the risk of dumping money, only to lose, if you want to pick up XIII. XIII has a really different feel when you first play it, which is why I think it doesn't matter too much which KOF you should play to prepare for XIII. I play quite a bit of 98 on GGPO and 2002UM, and I still haven't completely adjusted to XIII, but that's mainly because I haven't played the game enough.
You can't go wrong starting with those three characters, though Iori has changed noticeably going into XIII; he's still a very good character, regardless. K' pretty much plays the same and Kyo plays like his '95/Kusanagi version. All three of those characters are good, and if you REALLY can't get away from uppercutting and fireballing...I guess you'd be fine sticking with those characters. Personally, I don't think the learning curve is so high that it'd be difficult to learn more than three characters, because I'd find it really boring to play only one to three characters ever in any fighting game.
Like in SF, spacing is very important part of the game. KOF offers more movement options though, with hops, rolls, and backdash cancels. That also makes a KOF match much more high paced, and rush down-based. I think the thing that seperates KOF from SF is that most characters have tools to deal with many situations, allowing you more offensive and defensive options.