As long as the campaign and the geofence have been downloaded to the user’s phone, the message should be displayed within a minute of the user triggering the geofence
Real-time geo-messages are delivered via local notifications - not remote push - so they can display as soon as possible when triggered; they can even display on devices that are offline entirely, as long as GPS or WiFi are enabled.
Caveat: Depending on the device, if a user has a low battery, it could take up to 5 minutes for a message to be triggered (because phones check their location less often as the battery runs down in an attempt to conserve power).
To get a better background on Places & geofences read up on it here as well as more information on Messaging with Places.