JoenM8r is correct.
Mario Kart's online isn't as flawless as you would think.
Certain online games use different methods to compensate for lag.
Mario Kart (as well as quite a few console shooters) use a method where the host machine predicts what each player is going to do in order to compensate for lag. The end result is an experience that has no slowdown and appears perfect, but is in fact not.
This is why if an opponent is directly in front of you and you toss a green shell, sometimes it doesn't hit. Because the opponent isn't actually in that spot, but your connection to the server predicted that's where the player was.
For Mario Kart this isn't really a big deal. There are so many homing items and other weapon nonsense that autotrack that it's easy to think that the game is running lag free.
Another example pf online lag handling is in certain RTS (and other games) where if your connection to the server sucks, you simply lag. The game goes on without you and your PC has to catchup to what's happening if you lag spike. The game is on the server, your ability to participate in the game is based on your connection. If someone's connection sucks, then they'll appear to just be standing idle as if they weren't pressing any buttons.
Now we move to Smash.
With a fighting game, you need frame by frame precision. So they can't cut frames out online or make prediction guesses like Mario Kart (would it really be fun to smash attack someone, only to find out they weren't really there a second later?).
Input lag is simply due to bad connections. As connections get better, the game seems a little slow. Brawl simply slows down if there's too much lag, since individual frame precision cannot be lost.
The other alternative could have been (if Nintendo used servers, Brawl hosts connections from a host Wii) that if you're lagging you just stand there and take it while everyone else moves perfectly. That's not much better. Arguably worse, since you could lose a match due to a lag spike and your opponent would see it as you making a mistake instead of you having no control.
My point?
Brawl is based on connection speed. If you're friend and you aren't getting somewhat low lag in online matches, well your connections suck. Brawl runs off of your two machines connected together, the servers exist only to connection players, not host. Meaning your connection sucks and the lag is on your end.