what is the best online storage service for time machine

There isn't any, the reason is TimeMachine is a backup of your entire boot drive, can be many gigabytes in size which Internet Service Providers only provide a fraction of upload speed compared to download speed so it makes online backups rather impractical for most.

You can share some files via a service like DropBox between remote computers, but to backup your whole system it's better to have it stored locally.

After all how can you restore your hard drive if OS X isn't running to get online?

https://discussions.apple.com/docs/DOC-3045

If you want secure storage Time Machine is obviously no good, use Carbonite or SugarSync, avoid Dropbox. Next do a clone regularly, CCC is good for this as it can schedule incremental clones. This way you have a full system backup no older than your last clone and a data backup no older than the last time you connected to the internet.

ds store wrote:

There isn't any, the reason is TimeMachine is a backup of your entire boot drive, can be many gigabytes in size which Internet Service Providers only provide a fraction of upload speed compared to download speed so it makes online backups rather impractical for most.

You can share some files via a service like DropBox between remote computers, but to backup your whole system it's better to have it stored locally.

After all how can you restore your hard drive if OS X isn't running to get online?

https://discussions.apple.com/docs/DOC-3045

Why is local storage better than offsite? I had a house that burned down and can tell you from experience that local backup was totally useless.