I don't use skydrive, hence the reason that I didn't comment originally. I don't even consider it because it doesn't work on Linux. In addition, I think it has a 50MB file limit....which makes it a little harder to really make use of that 25GB of free space.
For me personally, I use dropbox. It works on Windows and Linux as well as on my Droid. I get 2GB for free by default, but by having other people sign up based on my referrals, I think I am at 3.0GB for free at present. I like dropbox as it's simple and the sync feature that keeps files both on my PC and in the cloud is a benefit that I enjoy. For $9.99 a month, you get 50GB of storage space. For me, I like the fact that there is no file size limit with dropbox. You are only limited by the size of your dropbox account.
A few friends of mine use box.net. If you are an Apple user, they have been giving away free 50GB accounts. For free, you get 5GB. I know you said you wanted more than 5GB, so this might not be enough for you. Box.net has more features when it comes to security and control, but the free account does not automatically sync. So, you have to manually copy your stuff up. This has a 25MB file limit.
Another option is SugarSync. Again you get 5GB for free. And this one does sync, like dropbox. If you want to pay $4.99 a month, you get 30GB of online storage space. I think Linux support is a little lacking here...they seem to focus more on the mobile market.
Here is an article with some information on the above; Dropbox vs Box.net vs Sugarsync Head to Head Review - Damang Media
Mozy probably isn't a good fit for you, as it doesn't offer Linux support.