Actually, wait a couple of weeks on KoF XII. They should have a new patch coming out soon that should make the online play much better. As of now, online play sucks outside of Japan, and if the patch doesn't remedy it then the game pretty much sucks unless you have friends to play offline with. Single player mode is essentially non-existent - it's just a Time Trial arcade mode with incredibly stupid AI. If you do have friends to play with, the gameplay is great and I'd recommend it fully, otherwise wait for news on the patch to see if it does its job.
Blazblue is a really good game, though it plays a lot different than SF/KoF. Gameplay is much faster than SF but I would say a good deals slower than MVC2 - it doesn't seem hectic enough that I lose track of what's happening but it can be a bit troublesome at first if you're just coming off months of SFIV. The game is really combo heavy and you'll have to just learn your combos if you want to get past that beginner's level. It really makes this game fun though - I've had a lot of times where I was down to maybe 10-20% health and the opponent like at 80-90%, but I was able to pull off a couple 4000-5000k+ damage combos and get the victory (and the same has happened against me, though). You really have to lose, and probably lose a lot, before you really start showing real signs of improvement. Each of the 12 characters are really unique, though online seems to be dominated by Ragna/Jin/Noel/Nu from what I hear. I personally get a good mix of characters, though there are some like Carl/Taokaka that I see much less than most. Online plays lagless/near lagless as long as the connection is better than blue from my experience, so there shouldn't be any problem there. Game is overall really solid, but I really don't think it's beginner friendly if you just plan to play it casually online. Balance is probably an issue too - Nu can do sick combos with sword, Arakune's curse is probably bordering broken status, Rachel can zone and pressure well - as long as she has a pumpkin out anything she does is essentially safe, Carl's near the top because he has an infinite, and then you have a character like Tager that basically sucks against the top 3 and does maybe 50/50 against the rest of the cast. SFIV is a lot more balanced that this game and if you really don't like a game with overpowered characters this may not be for you. It's definitely one of my favorite fighters this gen and I'd definitely recommend it. Game is much more polished that KoF XII offline too - it has decent single player options, though to me online is really all that matters and Blazblue manages to get that right and then some. Definitely get that game unless you completely hate combo heavy, tier-whored games. Though the tier-whoring is probably only for more advanced tourney level play - online you'll get a nice mix of tier-whoring and non-tier whoring players.