If you adhere to documented approaches, you are stuck in writing two applications.
However, Dianne Hackborn indicated that there is an undocumented android:required attribute in the <uses-library> element in the manifest. Basically, you can set this to false to complement Google Maps. In principle, this should mean that if Google Maps is on the device, you can use it in normal mode, but your application will be installed on devices that do not have this. You will need to use Class.forName() or something to find out if Google Maps classes are available to you before trying to call startActivity() on your MapActivity (for example, turn off the selection of the menu that launches the map).
My sincere hope is that this is documented in a future version, and until then you risk that it does not work, being somehow corrupted by the device manufacturer, etc. If nothing else, watch him when the Gingerbread Cookies and hopes that they were documented at that time.