Thanks all for the tips. Just got back from the trip and am suffering from jet lag. Anyway, here's an update of my experience with Wifi-Korea (copied and pasted from another forum):
So just wanted to update for anyone interested. I rented the ESP (everywhere speed pack) from Wifi-Korea, wifi-korea.com, and it worked out nicely. Not sure about the UDP (Wimax) but the ESP literally worked almost everywhere (uses LTE). I prepaid for the ESP (around $30 for 7 days of usage + $100 security deposit. Also a $5 delivery charge) I had it delivered to my hotel in Jeju and it was delivered on time without any issue. I had to leave it with my hotel's front desk in Seoul for return and that was $5 additional plus an extra day or two of usage that came out my security deposit. No big deal, and it was well-worth it. Battery life was good and the device lasted pretty much all day. Speeds and coverage were excellent. I was able to use Google Voice/Hangouts to make international calls just fine. I think this was probably the most cost-efficient way to go since I was getting LTE speeds + voice calling (per Google Voice rates, which are extremely reasonable). The only downside might be that they hard-cap you at 500mb, which is also good in the sense that you won't end up incurring overage charges. But once you've hit 500mb, you're done. This happened to me one day because I connected my laptop and forgot that I had Crashplan running and it probably sucked through 500mb in no time.
So as a word of warning, make sure you disable any auto-backup/auto-archival apps, software or processes on whatever device(s) you plan to connect to the hotspot. After that little incident, I disabled almost everything and my data usage fell to acceptable levels, even with Google Hangouts usage and whatever else. We primarily used it for Google Maps, Google Hangouts, Tripadvisor, and local app usage (Metro maps, Audio Guide apps, etc). It worked out really well.
As far as "free wifi" hotspots in Seoul (and elsewhere), yes there are plenty of hotspots but most are not "free" - I saw a lot of "T Wifi" and "Olleh" hotspots, which are the pay as you go ones of course. So if you have a plan or pay for it, then yes there are plenty of wifi hotspots available. I think a lot of people fail to mention the "pay for" part and everyone else assumes it's free.
I should also mention that the EG Sim card I ordered arrived too late by the time we left already on Jeju. Apparently there was a Korea festival going on the week before the trip, when I ordered the SIM, and that caused everything (including mail/deliveries) to get backed up and delayed by 1-3 days. Such was the case for me - the SIM card was supposed to be delivered on 9/13 and didn't arrive until 9/15. I ordered somewhat late on 9/8 (but with a 5-day shipping estimate from the date ordered so cutting it close), but had no idea about this festival and that it would cause such delays.
I had to get the hotel we stayed at to return-ship the SIM card for a refund but EG hasn't confirmed that they've received it. I may have to file a dispute with my credit card company if I don't hear back from them soon; they seem to take their time replying to emails and keep telling me they haven't gotten anything every time they do respond. Aside from not getting the SIM for my parents, things kinda worked out as their friend let them borrow a working-phone and we would just call the friend(s) they were staying with to get in touch with them. But it was super inconvenient at times not being able to reach them...
I'm not too happy with EG but I guess I can't really blame them for the mishap either. They should have at least warned customers about a delay though due to this apparently huge festival. I think if the festival wasn't going on at this time, it would have shipped a day earlier and arrived a day earlier. Oh well, at this point I just want the refund but they seem to be taking their sweet time... I don't think the mail/delivery is *that* slow.