Hrm. Maybe a tables of countries, a table of states, and a table of cities? 😉
Well, you asked.....
When you say "speed of initial selection of location", you probably should give more info. There are several ways to handle data, as you might imagine, and PHP is only one of them (although it's the one we're concerned with here). I've seen some pretty "quick" interfaces recently that used Javascript to read an XML file without a page refresh. If you're comfortable in Javascript, etc., that might be a go.