There's plenty of options here.
For the Nokia you can use Ebuddy or Nimbuzz which can access the major IM services including Gtalk, or one of the official clients like Windows Live Messenger.
I don't know the Blackberry apps too well but there's Yahoo, Gtalk and Windows Live clients for it.