Most of the modern online systems knock spots off Sage in terms of usability and reporting. It does its job but I believe that underneath it still relies on a very old flat field database, and other programs are based on a more up to date model. It shows.
I looked at 8 of the online systems, and chose Xero at the end of the comparison. The reasons were varied, ranging from lack of user access control through the user interfact to the level of reporting. All of the programs that I looked at have moved on, so the comparison would be closer now, but Xero has moved on as well. It's been the system that I use for my own accounts for over a year, and I'm very happy with it. The time saved on bank reconciliations alone makes it worthwhile, and that's without having the automatic bank feeds. I have a dozen clients using the system and the basic feedback is that they like it and find it very straightforward
You say that you are not working in one part of the world, so multi-currency might be important to you. Check that out in the systems that you look at.
One option that hasn't been mentioned that I was quite impressed with is e-conomic. Along with Xero that strikes me as being most suitable to scale up to larger systems - not that all of the others can't of course
