I love my GripMat! http://www.gripmat.com/
It's a thin, spongy material, but the printed side has a bit of stickiness to it, not with adhesive like flypaper but rather more like the grippiness on the bottom side of the FFG neoprene mats. The grip can take some getting used to, maneuver templates don't slide around if you use too much pressure. I've had the mat for close to a year and it shows no wear, and numerous layers of "nerd grease" (from elbows, arms, etc) have made the surface just perfect.
I started with a GaleForce9 mat and gave it to a friend and his son who were just getting into the game, only because I didn't see the need for another mat. More slippery than my Gripmat, and tended to scuff over time from templates and bases. Still beautiful though.
I've played on the magnetic mats; they look great but if you're an opponent who doesn't have magnets it's like playing on an air hockey table and can get frustrating.
I like the look of the FFG mats (Bespin looks SO good) but still can't wrap my head around why they made them so slick.
As for graphics, go with what appeals to you but I'm fond of simple starfields and planets. As mentioned earlier, the asteroid mat can be distracting, and there is a "Death Star Surface" mat that about gives me an aneurysm every time I see it.