"Android is upgrading... Starting Apps" on boot
I seem to have found the solution for my issue.

After posting the initial question I started noticing every so often I was getting a message saying that Aces Bubble Popper has stopped responding.

I have not used this game in a very long time and haven't updated it in an even longer time.

Apparently this app has permission to run at start-up (why a game needs that permission, I do not know and wish I could disable).

After updating the app, I am no longer getting the messages that the app stopped responding, and I am no longer getting the "Android is Upgrading... Starting Apps" when my phone boots.