I've had an Android G1 phone since late October (verdict: I hate it less than other phones). There are plenty of useful/fun apps in the Android Market, but today I downloaded my first game-changing app: Android Calling Card, which auto-dials any cheapo calling card you buy down at the corner store, and the PIN, and then any number from your address book, automagically. It supports multiple cards (the cornershop card-array is very country specific — Eastern Europe, USA, China, and other nations all have their own cards) and unobtrusively shims itself into the phone's built-in dialer app.
I just used it for an hour-long overseas conference-call — the kind of thing that used to cost me £20 or £30 — and the total cost was £0.51! I hate how the mobile carriers gouge on long-distance, so I get a grim feeling of satisfaction knowing that I'm depriving Orange UK of the gigantic sums it used to charge me for staying in touch with people elsewhere (of course, I'm also pissed at Orange because an operator named Colin boneheadedly kept on insisting that I'd somehow used 37GB of bandwidth last month with my phone's 3G networking — something that would require me to watch YouTube 24/7 every day of the month to even approach!).
I can't see any reason why this app wouldn't work when I'm roaming in other countries (I have a T-Mobile SIM I use when I'm in the US) — I'd just have to drop a buck or two on a local calling-card to work with it.