The only 2 KOF games I have are 2K and 2K1 (both MVS). I prefer 2000 to to 2K1 because the animation seems smoother, but I prefer 2K1's option to choose how many strikers you want. I prefer the music in 2000 to 2k1, as 2K1 feels repetitious (sp?) and uninspired.
The gameplay speed seems about the same to me, I put them both in my MVS last night and played 2K then 2K1 and didn't notice any speed differences. I do think the characters sprites are bigger on 2K1 like the_colonel said, but the animation suffers IMHO.
I think 2K and 2K1 are excellent games with flaws. A lot of people blast 2K1, but I think it's 'cause they won't give it a try or give it a chance.
Ao anyway, if stranded on a desert island and was only able to have one of the 2, I'd got for 2K.
Hopefully 2K2 will drop some characters and/or have a higher meg count so we can get some smoother animation and higher quality sprites. As for innovations, I think every KoF has innovated at some level from the previous version, so I think it's a safe bet they will do something to innovate this time as well. ANd if not, then you are correct the_colonel, we have another Capcom.