Definitely go with the 3/4" Marine Grade Plywood (7 layers). We used the same stuff to replace part of the decking on our boat dock. Then I put 2 coats of Restore on it to give it texture - we chose a nice blue color since that is the only thing you will see blue on Eufaula (very dirty lake).

If you have more specific questions or want more ideas, check out the Restoration section over on the Pontoon Boat and Deck Boat forum http://www.pontoonforums.com/viewforum.php?f=16

(moderator, if it's not okay to post links to other forums, please delete this link).