Note: although never a soldier, I've played one on TV (and fired the M16 as well as a few other fun toys).
One reason for 5.56mm (not caliber) ammo is that it's lighter than, say, 7.62 mm or .303. A heavier bullet requires a heavier charge, which may require a heavier casing, etc. etc...so you can carry a bunch more 5.56mm ammo around with you. This is a Good Thing.
The primary advantage of the M4 is that it's smaller, with a carbine-type stock. I believe it's mostly being phased in (at least for now) to the light infantry units such as the 10th Mountain and 82nd Airborne. Even in those units, however, there's a few M16 carriers who have the M-203 grenade launchers.
Many of the well-known early problems the M16 had (it jammed, it blew up, yadda) were in fact caused by a combination of factors, not least of which was that Olin America (who, I believe, made the ammo) used a powder mix with a good amount of calcium in it. This tended to collect in the weapon, and when combined with the carbon present from combustion, formed...yup, limestone. This, coupled with the M16's less-than-handy cleaning charateristics (it comes apart real easy; getting the doohickeys into all the thingamajigs and scrubbing is the problem) meant that it would quite frequently jam up or even blow back. Cartridges would strike lumps of calceous deposits in the gun and refuse to seat, load or eject properly. Since then, different compositions of propellant as well as new cleaning guidelines (and a few design changes) have pretty well dealt with this issue. Roninspoon also reminds me that the design spec for the barrel was changed to include a chromed interior barrel lining to reduce build-up.
Finally, as to full-auto - why would you want it? You'd really prefer your riflemen to at least pretend to be taking aimed shots, since they have limited ammo. You have SMAWs and SAWs for suppressive fire. In any case, you'd just have to clean the weapon sooner for less useful time on range/in the field.