Never been to any of these, but we're going to Prague in the Spring, so I looked up Prague in my Zagat 2006 Europe's Top Restaurants. Top 10 for Prague are:
Allegro--Italian/Mediterranean
David--Czech/International
V Zatisi--Czech/International
Flambee--Mediterranean/Seafood
U Zlate Hrusky--Czech/International
Rybi trh--International/Seafood
U Modre Ruze--Czech/International
U Modre Kachnicky--Czech
Kampa Park--International/Seafood
Mlynec--International
Be interested in your evaluation if you try any of these.