Any Smartphone can do items 2 through 5 on your list.
For US and Europe you will want a GSM triband phone. Perhaps even a quad band phone if you use Cingular or AT&T since they've started using the 850MHz band in the US. However, there are no quad band smartphones out yet. The US uses 1900MHz (with some 850 recently added as mentioned), and Europe uses the 900MHz band.