I'll take this one at a time:
Authentication does come with an overhead, yes but is usually small enough to not be noticeable. I would suggest not having a public MongoDB endpoint if you can avoid it, just from a general security perspective. Or at least lock it down significantly if you do. Also, make sure you use at least version 2.0.6 because of this bug which I have seen have a significant.
You can use your favorite tools - chef, puppet etc. to deploy, but unless you plan to do this multiple times or to expand into multiple shards the set up is not massively complicated for a single replica set - for three members, once the instances are started it is basically a handful of commands to configure the set (rs.initiate() on the first, rs.add() for each subsequent member). The real meat of configuring EC2 when it comes to MongoDB is the EBS storage piece, filesystem etc. See here for the various recommendations on that front:
Ubuntu or RHEL/CentOS is essentially a preference call on your part - do you prefer apt or yum, rpm or deb, SysV init or upstart? Either way, there are repos available from 10gen to keep up to date with the latest version of MongoDB:
In terms of the recommended version, I would usually recommend the latest stable version with long term support - currently I think that would make it CentOS 6.2 and Ubuntu 12.04