I would second the Pontos deck. It's thinner than the Nautilus decks and has a good backing "glue" to it that will hold it down firmly. Pre-stained, as mentioned before.
In the interest of full disclosure, I did provide them with tons of research for their Essex PE set. I don't have one myself yet, though, so I can't comment on it, biased or not.