These are the best booties I have owned.
http://www.neilpryde.com/2000/2k-lc-round.html
Comfortable and very robust and they seal well enough to keep sand and shells out. I can tuck my wettie legs into them for a better seal.
Booties in general, and these ones in particular, give far better grip than bare skin, both on the deck and in the straps. So much so that I do not use wax or deck pads on my SUP or surfboards I use for kiting. The booties grip fine and I can get them in and out of the straps with no problems.
I have fairly big feet and I think they're wide across the toes. I normally wear a size 46-47 shoe. My booties are size 43.
None of us will have any idea how freaky wide your feet are so I cannot hazard a guess as to how you will go. All you can really do is try some out.