I think maybe the referenced libs was not my only problem (as you may have sensed). I was also doing a few other things in the UI thread which I should have been doing in a worker thread.
I have a pretty smooth loading app now, thanks primarily to three things:
1. Using a custom style/theme to set the background image of every activity so that the screen is not completely black while it's loading.http://android-developers.blogspot.com/ ... speed.html
2. Do a few first-time heavy tasks (access referenced libs, copy a sqlite database into place, etc) in a worker thread using AsyncTaskhttp://www.screaming-penguin.com/node/7746
3. Showing a progress dialog while referenced libraries and database copying was happening only the first time you run the app. Hitting the referenced libraries for the first time still does take a few seconds, but now there is a "First Time Loading" dialog to let the user know there is not a problem.