I remember back in the day a 700 kb map would take forever to download. What is it like now? Can we have like 20 mb map file sizes and they will download in seconds for the average person?

I don't recall how long it takes, depends on the person but it is definitely significantly faster.
For a personal example:
A 4 MB file before remastered used to take like 20 minutes to download (or more)
The same 4 MB file now will take approximately anywhere between 30 seconds to 5 minutes. I noticed that sometimes it can take 5 minutes, and other times its super fast with only a few seconds. Hope that gives you an idea. In terms of downloading any map that is 5 MB or less, you shouldn't have to worry to much (which means sound effects don't cause such an annoyance when sharing over Bnet)

The possibilities..... (plays the cable guy gif)

I posted this in the shoutbox as well, but reposting here for posterity: OhMan taught me that if you play a map by yourself on battle.net before hosting it publicly, it makes it so players download it super fast before entering the lobby, but if you host it for the first time publicly then people download slow in the lobby like old SC. He currently has a map that is ~30MB that downloads super fast as long as he hosts and starts and leaves a game by himself first then hosts publicly, when he forgets and hosts publicly without playing it solo first, the downloads crawl.

I should also add there is a delay between when you quit and remake and when the fast download actually is enabled. I suspect that delay is just the length of time it takes Blizzard's servers to upload your map to their own servers. So to be safe wait like 5 min before rehosting, otherwise just tell people to rejoin if they join in and are still DLing.

At this point I would not be surprised if a thread was made asking how to do a flash animation....

A 20mb file takes 3 seconds to download for the average person.