Hey Guys,
Got a new hosting service and the install of J2.5.4 and CiviCRM 4.1.2 worked first time without any problems whatsoever.

In the process I found several other hosting services don't support Innodb, and are not in any rush to do so, and some don't even know what it is. (I'm no expert, but I can take a few minutes to read a wiki and figure it out a bit. This is supposed to be their business and they don't know what INNODB is!)
My recommendation to anyone having problems with installing is to DO YOUR HOMEWORK, and follow the first piece of advice on the Installation Page
"Before beginning the install process, please verify that your server meets the requirements for CiviCRM 4.1." ... my bad, I just assumed my host would have the requirements.

So I hope my experience helps someone else!
Here's the results of my homework:
I didn't find ANY hosting service that posted the specs that you *NEED* to know if you want to run CiviCRM. You have to contact them!
Most sites that I emailed to try to get info regarding their specs, did not actually read my email and just gave me a blanket "yeah we do that stuff" kind of answer.
You have to press them with specifics - I had to email back to several and tell them "They didn't read my first mail and I need to know..."

One host was still running MySQL 4.x and wanted an extra $5/month to upgrage!!!

WTF!?? Go pound sand!
Another hosting service response to my inquiry about INNODB was (and I quote) "Thanks for your email, we have checked and we do not have INNODB. We also do not have any experience with this particular program, and unfortunately, have no suggestions. My apologies for the inconvenience." (end quote)
"...that program

" I bet they run that other program too! what's it called ... Linux or something! Jeez, I'd have a lot of confidence contacting their support department!

Anyway, I finally found a hosting service that had all the requirements, answered my questions intelligently, and cost less than the $5 "upgrade" for MySQL 5.1.x that one company wanted. The install of J2.5.4 and CiviCRM went smooth as silk!
Final word.
DO YOUR HOMEWORK!
Oh ... Herschel, I think there's two pages out there that give different mem requirements. This one:
http://wiki.civicrm.org/confluence/display/CRMDOC41/Joomla+Installation+Guide+for+CiviCRM+4.1says 64M in the "Trouble Shooting Resources" section. I did see the other one that says 128 M but I can't seem to find it again at the moment.
Thanks again guys!