Tortoise is definitely the way to go... we actually use it with Mercurial/Kiln. We set up the Eclipse client because we really like working with Mylyn but we end up doing most of the work with Tortoise. It's faster and it gives you more insight into what's happening.
We switched from CVS (although most of us had used SVN before too) to Mercurial and it was a rather difficult adjustment for our team, but mostly because of the way we set up our repositories. We used the Fog Creek-recommended method of setting up Dev, Test and Prod repos, then doing development in Dev and pushing up, and bug fixes (more like hot fixes) in Prod and pushing down. Getting into a rhythm with that was difficult and we ended up with some merge nightmares. But once we got past that, it started working out well.
If I was going to make one recommendation, it would be to start out as a single team member with a single repository until you get used to it, then gradually work in more committers and more repos when you are comfortable. You think that "ok, I have to commit, then push" sounds simple, until you run into all the questions about pushing between repositories and running into conflicts with team members and such.
Hope that helps - good luck!