Thank you, Skip252. I can definitely time how long it takes my tracks to change with my digital watch. 2 seconds with internal memory, 5 seconds external (4 GB data), 10 seconds external (9 GB data). Something is definitely wrong.
My library is totally flat (no subdirectories). That works best for me. Tonight I took my 4GB library and created 25 artificial subdirectories and populated each with 50 songs just to try giving it some "structure". The database refresh took 13 minutes and track-to-track time is still 5 seconds (no noticeable difference from the "flat" structure). I don't know if creating 200 subdirectories would be worth the effort.
I'm open to suggestions. I'm about to jump out a window.