So, I'd like to answer my question on how to make this possible in the easiest way.
My objective was to display a DialogFragment whenever the Service requested. The difficulty with this, is that my Handler was an inner-class to the Activity that hosts the DialogFragment, this was causing LifeCycle issues when I tried to call the DialogFragment.
To achieve this with essentially next to no work, I created a transparent Activity that looks like a Dialog, instead of using the DialogFragment. This simplified everything because I don't have to worry about an IllegalStateException when starting an Activity. So everything works as intended now!
Thanks for the suggestions, but ultimately, if you come across this exception, see if you can simply create a dummy Activity to launch your target Fragment from. This will simplify the LifeCycle issue tremendously!