Waze - Waze is the world's largest community-based traffic and navigation app.
TeamViewer - Proprietary, but very handy VNC viewer.

+1 for Skype.
Viber - A skype-like (but more handy). [Maybe one day ]
Linphone - A VOIP app.

A tracker (if your phone gets lost or stolen).
A QR-code reader.

The "Littré" - Open-source XML dictionnary for french people.

Sybu XBMC - Remote control XBMC.
A DLNA Player.

Jamendo app - Free music.
SoundHound or Shazam - Recognize a music by singing it or recording it.
+1 for an ebook reader

That's what I'd like to use on linux phones...