Ubuntu has had the
Ubuntu Software Center for quite a while now, in Internet years, and it's a front-end to apt-get, basically, but it's entirely graphical and laid out in a logical and straightforward fashion. I didn't say it was the
best implementation of a repository-style app market environment, but it sets out what it accomplishes to do fairly well for users unfamiliar or uncomfortable with package management (which sounds scary if you're unfamiliar with the terminology).
As much as I hate the closed nature of Apple's App Store and the sometimes-ridiculous approval process, I'm not a fan of the Android Market for this reason. Before I installed DroidWall on my rooted HTC Magic (aka the MyTouch 3G, the second Android device released in the US), I only installed apps that were recommended by a moderately reliable source, such as Lifehacker (not much of a fan of the rest of the Gawker network, but LH is okay) or ones where it looked particularly good and the permissions were sane. I'm a little more fearless with DroidWall when it comes to checking out an app that seems even a little sketchy, because DW's default is to block wifi/3G connections, so it only gets net access after I check it out and see if it's obviously crap or not. At any rate, if the market system worked like a collection of repositories and users were freely available (though the carriers would probably attempt to lock that down) to add trusted third-party repos to their market. Maybe not with Google Checkout payment support, perhaps, but it could be done. If Android Device X shipped without a wifi tethering app/option and the carrier's subset of the official Google Market doesn't list wifi tethering apps and yanks new ones as they're added, I'm sure someone would happily host and write if necessary a tethering app for free and slap it on a repository with a very good community reputation in next to no time, simply to fix that fascist omission.