COMMON GROUND
THE ISSUE
So as I promised, I did find an answer, after rougly a week of digging into how fix the "starting" trouble. I read through every forum and bit documentation I could find, trying to both understand as much as I could about this dreaded concept, and find a reason why it wouldn't work (I reviewed logs in Verbose mode from Windows, and both the SharePoint diagnostic and IIS logs via ULSViewer). According to the logs, I could see SharePoint attempting to work with FIM and would get so far as "ILM: Created Certificate". Following this, nothing would come from UPSA (Other SharePoint activities would continue on). No failures were reported. No errors were captured. It remained this way (I left it on "starting" for 24 hours) until I purposely terminated the service instance and killed the "UserProfileSyncSetupJob" in the timer queue. Each attempt would successfully create one Forefront certifcate (MMC snap in for "certificates", Computer Account) in the Trusted Root Authority folder, and everything I could find on the subject indicated there should be two within this folder when successfully completed, but noted they would be almost indistinguishable from each other, as both are named the same. I'd faithfully purged the one within the Trusted Root Authority folder each attempt.
THE ANSWER
I'll caution you; there are some very interesting forum posts out there, offering some wild advice on how to resolve this issue, most of which suggest deleting and recreating UPSA. Please note - THIS IS LIKELY NOT NECESSARY. For my case, I finally discovered (With the help of an inspired person's comments off a related post) that certificates are created in both the Trusted Root Authority folder AND the Personal folder. The Forefront certs have to be deleted from both for the service to start, as FIM creates one cert in Trust Root Authorities AND another in Personal.
THE END
I truly hope this helped someone, as this killed almost of a week of my time. If you should observe a collection of Forefront certs building up in the two folders, (IF UPSA is stopped) it is safe to purge these (The certs will be recreated, when successfuly restarted or "reprovisioned" as Microsoft likes to phrase it). Good hunting to you!