Yeah, sounds like something's not right. The iPhone itself shouldn't need to reboot. I've installed almost 50 apps now and it just shows the icon with the loading progress bar below the icon (as it's actually downloading) then shows installing which sometimes takes awhile, then the name of the app once it's ready to go.
Do you have the first iPhone or the iPhone 3G? If the first iPhone, did you jump the gun and install the "unofficial" 2.0 update or the official update through iTunes updater?