For relatively low DPI (800), I've had a very good experience with Razer Sphex, which is a very thin layer of polycarbonate you can stick onto your table. Gave me the best control over the mouse, compared to any other mat I've tried (I especially hate the ones covered with fabric).
Although they issued "Razer Sphex V2", which is awfully colourful, you may be lucky to find the first version, which was solid grey.
