As others have said, just get stuck in. A phrase book is useful to establish a script, but as others have said as soon as the other person deviates from the script you are stuck. I wouldn't worry about vocabulary and grammar, "bidon" is indeed the right word for water bottle, but "gourde" is understood as indeed is "bouteille". It al works. Let's be honest, if you ran a cafe and a cyclist came in waving a bottle and asked for "water for my jar" you wouldn't laugh him out of the shop.
S'il vous plait can indeed go at the start of a sentence and is not at all odd. It's generally used to attract a waiter's attention, as we might say "excuse me". So if you stop someone in the street with "SVP" it can be viewed as shorthand for "excuse me please" and is acceptable. Bonjour is actually better usage though, and buys you a second to think of what to say while they are replying "bonjour m'sieur/madame." You can also, with thought, buy time with your sentence structure, eg:
"bonjour" (time, think)
"je cherche, SVP..." (I'm looking for, please...) (more time)
"Un cafe/le supermarche/le village de..." (more time while you produce the map) and so it goes on. Bear in mind they don't want you to fail.
When you get proficient you can learn such useful phrases as "Salaud! Putain de Dieu, t'es aveugle ou quoi? T'as trouve ton permis ou, dans une pochette-surprise?" (Trad: "B*stard! F*ing Christ, are you blind or what? Where'd you get your licence, a lucky bag?")
This and other juicy phrases are not advisable for novices though, you need to have the skills to talk your way *out* of trouble before you dump yourself in it.
. 
C'etait sur le table. Et le freakin' chat mange le poulet!
