I've always been looking for a decent way to get fonts other than the basic web fonts into my sites without relying on flash or browser-specific hacks and without having to deal with licensing restrictions. I think I finally have a good solution. It's a service called typekit and it supports all the major browsers. They have a pretty decent library of fonts to choose from and integrating it with your site is as simple as adding a JavaScript snippet and choosing the CSS selectors for each font.
There are only a couple of downsides I see to the service, but they're not major. The primary one is that it does require JavaScript, so if your visitors have JavaScript disabled or run a browser plugin like NoScript, they won't see the typekit fonts. Also, while they do provide a free/trial version of the service, it is limited to a small selection of fonts and displays a typekit logo. For the most part, though, this won't be a drawback since the cheapest plan is only $25 per year.
I'm currently using the service on my blog and portfolio and it's a huge improvement. It really helps make the text more readable and a lot more aesthetically pleasing.