Jsem v trochu podobné situaci - sice jsem telefon neztratil, ale taky bych chtěl pořídit nějaký pořádný komunikátor.
Po celkem dlouhodobých zkušenostech s různými zařízeními se Symbianem i WM, s GPS i bez, s QVGA i VGA rozlišením, s 3G i HSDPA připojením - a po pročtení mnoha recenzí na N95 - jsem došel k těmhle závěrům:
1) Operační systém: dnes jasně WM6 Pro. Zařízení vyvinuté pro WM5 je už dnes škoda kupovat, o Symbianech škoda mluvit.
2) Rozlišení: VGA nebo větší. Když vyzkoušíš, už není cesty zpátky. Řekl bych, že ani malá úhlopříčka nevadí - ale to je věc názoru.
3) Připojení: HSDPA. Proti "obyčejnému" 3G je to rozdíl (ale samozřejmě jen pokud máš signál).
4) Interní GPS: není potřeba. Sice není na škodu, ale externí GPS má některé nesporné výhody - v autě obvykle lepší výhled na oblohu, v terénu nesrovnatelně delší výdrž (interní GPS je největší žrout baterie). Při použití navigace není externí GPS žádnou komplikací navíc, připojí se automaticky stejně jako interní.
5) Nezbytné samozřejmosti: Wifi b/g, Bluetooth 2.x, vhodný slot pro paměťové karty a procesor s dostatečným výkonem.
6) Možná to nejdůležitější: dobré ohlasy skutečných uživatelů. Kvůli rozpačitým ohlasům jsem třeba zavrhl Toshibu G900, která se jinak jevila docela nadějně.

Slušný pramen, kde můžeš vybírat: http://pdadb.net/index.php?m=pdalist&list=vga

P.S. - Tyhle mašinky vypadají slušně, bohužel ty nejzajímavější z nich budou mít zpoždění.