I'm not going to take credit for this fix, it all goes to BurgessJacob and Kanemura at GameFAQs, who figured out the tricks here. But since their solutions are spread out among 4 pages and a dozen posts, I thought I'd sum it up in one neat article:

Note: This fix is for people who can play with friends online, but can't play "with anyone" anonymously. If you cannot connect to WFC at all, there are probably other problems with your setup.

You will need to have access to your router's administrative controls to do most of this. If you have a linksys router, you can access them by entering 192.168.1.1 into a browser window. If you have a different router, just Google your router's name along with "admin" or "config" etc.

First, assign your Wii a static IP address.

1. Set your Router to Static IP mode, instead of DCHP. There will be a field to set the "first" IP adress for machines connecting through your router. It will probably be something like 192.168.1.100.

2. In your Wii connection settings, go to "change settings" and set your IP address (under no-> advanced) to 10 more than the starting IP above. So, if yours starts at 100, set your Wii to 192.168.1.110. Copy the SMask and Gateway information from the main screen in your Router info.

3. Set static DNS addresses. There are fields for this in the Static IP options for your router. I set mine to something like 100.100.100.1 and 100.100.100.2. Set those as your Wii DNS settings on the next Wii option page.

4. Before going on, test your settings. You should be able to pass the connection test. If not, double check your numbers.

5. Disable the "block anonymous requests" option in Security.

6. Port forwarding. For Linksys, go to Games & Apps and open TCP ports for 28910, 29900, 29901, 29920, 80, and 443. For instance, make profiles named Wii1 through Wii 6, and put 28910 to 28910, then 29900 to 29900, etc. Mark each port as "enabled" and set to TCP. For UDP, open a 7th profile for ports 1 through 65535. Finally, for all ports, set the IP's last three digits to match the IP you set for your Wii.

7.  This may not be necessary, but under Games & Apps turn DMZ on for the same IP as your Wii.

8. Set the Wireless channel to 1 or 11. This is highly recommended by Nintendo. Should be under Wireless options.

Save all your settings as you go along, and reset your Wii. Make sure you can get online with simple things (connection test, internet channel, etc). If you did this all right, and you were able to connect to the internet to begin with, it should work!

I went from timing out at the sandbag for every "with Anyone" Brawl to fighting 3 people in 5-6 games with low lag last night!

Thanks to all the help at GameFAQs. Now let's fight!