I want to point out a couple things here, since there seem to be a lot of misconceptions. 1) UEFI is not the problem -- it's one specific feature called 'secure boot'; UEFI is a very good thing overall, so we should point out the bad part and not the awesome whole, 2) MS isn't requiring that secure boot be required, or even that they have a signing key for it -- they're purely requiring that it be on by default, 3) the reference implementation and all known shipping versions of secure boot have a switch to disable it if the user so chooses, so it's not much of a lock-in facility -- it could be in the future, but it's not now, and MS isn't making it into one.
That said, despite being a huge Windows fanboy, Windows 8 is seriously making me consider switching back to Linux. This sort of lock-down is terrible for everyone, most people just don't realize how bad it is.
Matthew Garrett reported a while back[1] that some vendors will not provide an option to disable secure boot.
How long will it be until RIAA tells Congress that "Microsoft is not doing enough to stop piracy (even though they have the capability)", just like they are doing now with Google, and then gets them to remove "unlicensed" songs from your PC?
I think stores are fine. They are a pretty good way to show you the best apps for the platform, and they also help a bit with safety, but they should still allow you to download and install whatever you want from the Internet if you choose to.
Android has a pretty good model here. They have the Market, and then if you really want to, you can get apps from other sources, too. Although, I don't think they should even ask you if you want to "enable 3rd party sources" in Settings. It should be enabled by default, and maybe just give you a warning whenever you want to download a 3rd party app, just like they do in Chrome.
The point is I don't want to lose any of the freedoms of what I can do with my computer, just for the sake of having a store that streamlines app discovery and makes me safer when I use it. I should have both.