UPDATE 2015:
This question/answer still gets a little bit of activity, but it is over 5 yrs old and things have changed quite a bit. 5 years ago, the answer below was how I would have handled it. Later I wrote a very lightweight dependency injection solution that I was using for a while (which I mentioned in the comments). Nowadays, I would answer this question using Dagger and RxAndroid. Dagger to inject a "mediator" class into both the Service and all Activities that need to be notified, the Service would push the status update to the mediator class, and the mediator class would expose an observable for the activities to consume the status update (in place of the OP's broadcast receiver).
Original answer
I usually subclass Application and let my in-app communication go through this class (or have a mediator owned by the Application do the work...regardless, the Application being the entry point for the service to communicate with). I have a bound service that needs to update the UI as well (much simpler than yours, but the same idea) and it basically tells the app its new state and the app can then pass this information along in one way or another to the currently active activity. You can also maintain a pointer to the currently active activity (if there is more than one), and make decisions whether or not to simply update the current activity, broadcast the intent to launch a different activity, ignore the message, etc. I would also subclass Activity and have your new activity base class tell the Application that it is currently the active one in onResume and that it is being paused in onPause (for cases where your service is running in the background and the activities are all paused).
EDIT:
In response to the comment, here's more specifics.
Your application currently consists of Activity-derived and Service-derived classes for the most part. Inherently, you get functionality from an instance of the android.app.Application class. This is declared in your manifest (by default) with the following line:
<application android:icon="@drawable/icon" android:label="@string/app_name">
The application element in your manifest doesn't use the android:name attribute, so it just creates an instance of the default android.app.Application class to represent your global application context.
In my apps, I create a subclass of Application (ApplicationEx, for example) and I tell my app through the manifest that this is the class to instantiate as MY global application context. For example:
<application
android:name="com.mycompany.myapp.app.ApplicationEx"
android:icon="@drawable/app_icon"
android:label="@string/app_name">
I can now add methods to ApplicationEx for activities and services to use to communicate. There is always a single instance of your global application context, so this is your starting point if anything needs to be global for your app.
A second piece of this is that instead of deriving my services and activities from Service and Activity, I create a subclass of each with a getAppContext method that casts the return value of getApplicationContext (which exists already in both of these classes because they derive from Context) to my ApplicationEx class.
So........
All that being said, you add a CurrentActivity property to your ApplicationEx class of type Activity (or ActivityBase if you subclass it as I do). In ActivityBase's onResume method, you pass yourself to ApplicationEx for it to set CurrentActivity to that activity. Now, you can expose methods on ApplicationEx to pass information directly to the current activity instead of relying on the Intent mechanisms.
That's about as clear as I can make it