I've had my iPhone for about 3 weeks now, and I use it without a case. I've noticed that it tends to get warm quite quickly -- I understand that it's normal for the phone to get warm when you've been on a long phone conversation or surfing the web for awhile, but I've noticed that mine gets warm after about 3-5 minutes on the phone. In addition, it got warm today after checking my e-mail. It is by no means hot or uncomfortable (the warmest it ever gets is while charging), but it is warm to the touch, particularly on the back of the phone where the silver metal is.
I believe heat is correlated with battery usage...its electric metabolism. So you shouldn't worry about heat per se, especially if your battery is lasting as it should.