Before you use any type of protectant, you really need to do a good cleaning. Protectants will make it look good for a while, but won't last long if you put them on over a dirty surface.
If you can't get it thoroughly clean using your normal car wash detergent and a wash mit, you can use a good tire cleaner like A2Z and a soft bristled brush.
Use a protectant that leaves a matte finish and it will not be too slick to walk on. Armor All Original will be your best choice since it's the cheapest and you'll use the better part of a bottle.
