I haven't played Maya much, because I found it to be a deity-tier civilization and I prefer harder civs to play, but I agree that GS and plant it should be first. I also agree that CS quests matter, and thus the admiral is a good pick. Next I like the GE because there is always some very high priority wonder I would never get otherwise, and the GP point I get from the wonder eventually makes up for the increased GP cost. Next I like the prophet, because it is about that time that I finish Piety and I like to plant several mega-holy sites. The GWAM I like to save, for a couple of reasons: first, I like to leave the door open that I might choose Autocracy later. Pick up futurism first, and then get it. Second is that I might want to theme Broadway/Sistine/Uffizi later. Third is that all three are more effective later, after I get more puppets, tourism, and world's fair.
The Merchant can explore and discover CS, too, just as well as an admiral, by the way. But because of the increased GP cost you still might not want to do that, unless you've got multiple CS quests. I actually use my free MoV from Venice to do just that. If you have a good opportunity to early warmonger, though, I recommend not exploring at all.