In reply to Hardmanryan:
Initially, I think, you're confusing fit and size; they're not the same thing. Feet come in a variety of different shapes and, to accomodate this phenomenon, so do shoes; a good fit, therefore, is one that closely approximates your foot shape. A shoe that isn't a good fit, but is large enough to be comfortable, won't actually hurt; fine - except that it will probably also be neither precise nor sensitive. So, clearly, the first thing that a buyer must do is identify which models fit and which don't; and any reasonable range on offer will almost certainly include a few of the former. So try on as many as you can find. Try them in tight sizes; a tight shoe that also doesn't fit well will probably hurt in specific locations with "dead space" in others, whereas a tight shoe that fits will just feel....tight.
Once you've identified an actual model, the size you use will probably be best determined by what you're going to use them for; yes, I know - climbing! But is that entry level indoor climbing/hard indoor climbing/everyday outdoor climbing/everyday outdoor easy or warmup routes/outdoor "hardest edging you've ever done" routes - etc? I'm probably making that sound more complicated than it actually is; several of the broad use categories will happily be undertaken using the same footwear. As a (very) rough guide, I generally use suitable models of shoe in three different sizes - ie three adjacent euro sizes (inc halves), in my case 39, 39.5, and 40.(These tend to be La Sportiva Miura and Katana, so the fact that they range from tight to comfy, and that my shoe size is UK8, rather lends support to the idea that you need to go "small" with Sportiva.) The large size is probably the one that I would buy if simply going for what felt snug in the shop. The middle size would probably be a struggle to get on initially, but would soon feel a bit better and possibly wearable; once worn in, this is the size that I use most, and perfectly comfortably. The smallest size would possibly be dismissed in the shop as I probably wouldn't be able to get into them; but I buy them anyway because, with experience (ie many pairs of each), I know they'll fit with a bit of persistence and wearing in, and be the best thing in the arsenal for anything particularly small and edgy.
A cautionary point: the Sportiva models - and others - on which my experience is based are largely made of suede leather, which stretches; some shoes - 5.10 Anasazis, for example - are made of a synthetic material that doesn't stretch as much. This is probably common knowledge among 9 out of 10 climbers, but as it's maybe the 1(or fewer) out of 10 who need advice on shoe selection it's worth mentioning.
To (finally!) answer the question; if I were starting out again I would buy my "large" size - ie the ones that feel snug in the shop; they'll be fine on most walls indoors (I still use my old large ones with holes in the toes as a warm-up pair indoors) and at this stage you're unlikely to be doing anything on rock that will require the precision of a tighter fit. By the time you've worn them out and are looking for a replacement you'll have a much better idea of what you need, how tight they need to be, whether you could have used your first pair in a smaller size, whether it would be better to have a couple of pairs on the go instead of just one, etc....in short, you'll probably know the answer and won't have to ask.