Sounds exactly like a bad starter. Could be a sticking solenoid, but usually coils going bad. Each time you turn the key the inrush current "nudges" the motor a bit. It starts when it gets to a "good" spot. The number of tries usually depends on how far it last stopped from a "good" spot. If that's the case, replace it before you get stuck! It will only get worse, the part's not that expensive, and I don't think those multiple tries are good for the system.
BTW, is there a thread on this replacement? I had to do it for one of my cars last year (the Geo Prizm, I think), but couldn't access the starter without going way up from underneath. I didn't realize this until I set aside a day to do it! I had a Meineke do it since I don't have lifts, or a garage to work in. It wouldn't surprise me if I'll need this on my RAV at some point.
Wouldn't it be great if people posted whole DIY videos on this sort of thing (see the thread about the Google Video Beta)?!?! Actually, I'm a little surprised that say, Haynes, doesn't do this sort of thing on either DVD or as a subscription to a web-site. So, for example, you'd buy the Haynes manual, but if you wanted a more detailed "how-to," you could go to their web-site and buy a specific repair video, like trouble-shooting, replacing, testing a starter.
Todd