I've never had a good, smooth online experience with a fighting game or racing game. Racing games have gotten better simply because it's a little easier to predict where racers are going, but even the best ones still show warping or phantom crashes every now and then. Fighting games are just too reliant on getting the timing right on completely unpredictable actions between both players. As Reldan said, a lot of the blocks, parries, counters, etc are all decided in fractions of a second, which means even if you have a relatively perfect connection, the game still may or may not record your input at exactly the right time.
But that's neither here nor there for me, since I didn't buy SC4 for online play. I'm liking it a lot so far. The character creation thing is pretty cool, although there's very little documentation explaining what all the stats are doing and how you open up new abilities. I really really wish I could select "no voice" for my people, though. The limited selection are all really dumb and annoying and are made even worse by how many times they're repeated in battle. In fact, it's always been a pet peeve of mine for fighting games to have characters say one specific phrase during the different moves and almost all of them friggin' do it. Grunts and screams are sufficient, fighting game devs! Even worse, in SC4 the characters' stupid start/end-of-battle sayings step all over the announcer's stupid start/end-of-battle sayings, so you end up with a mish-mash of unintelligible audio stupidity.