SimpleDateFormat, the first time you try parsing (or, presumably, formatting) a date, will load in all the timezone data for your locale. This will take 2-3 seconds. It is hoped that this will be fixed in some future edition of Android.
In the interim, consider using AsyncTask to "warm up" SimpleDateFormat in your process before you need it. Just parse some date in the AsyncTask doInBackground() to get it to load the timezones sometime when it will not impact the user so much. Once initialized in your process, SimpleDateFormat will run quickly until your process is terminated.