I've played close to 40 ranked matches and maybe an hour or so of random player matches. Out of those matches, *three* were laggy. Out of those three, one had horrible input lag. The guy picked Kaede and just spammed one of his specials, and there wasn't much I could do about it. (Fortunately I was able to spam a few of Tung's specials myself and beat him anyway.

) This was against a player from Mexico, although I played two good matches against another Mexican player where the connection was good.
So there's no doubt about it- this game has much better net code than last year's SNK games.
Sometimes it doesn't even seem to matter if the other player has say, 260 ping. It will still be smooth.
Who are the easiest characters to start out with?
Here's a great beginner's guide:
http://www.shoryuken.com/wiki/index.php/NeoGeo_Battle_ColiseumGo to practice mode and mess around with everybody. Who do you like to use in Street Fighter?
Maybe to start with, check out Terry, Ryo, Robert Iori, Kaede, Jin Chonshu, Hanzo, Haohmaru, and Fuuma for your "FB/DP" characters, Washizuka and Athena for your "Guiles," and Mr. Big for your "Bison." King Lion is the closest thing to a boxer-type character; he's got rushing punches, a counter, but also projectile-style moves. Hotaru is really cool and can even change into a Phoenix stance like Xiaoyu from Tekken.
Most people say that the best characters in the game are Kim and Mr. Big, but I wouldn't pick your characters based on tiers. My favorites are Tung Fu Rue and Mai for the time being. Tung is fun as hell to use.
One thing you will find about SNK fighters is that they don't stick to the norms you'd find in other fighting games-- a lot of characters are more like "jack of all trades" types and have both charge and fb/dp moves. Also their grapplers are more unique. NGBC has a lot of characters that don't really play like other 2D fighting game characters.
And if you're used to KOF, this game may use some of the same sprites, but it doesn't play the same way. NGBC is more "Capcom-like," IMO. You'll find it easier to pick up and play than a lot of other SNK games, and (S)SF4, for that matter.