Managing large SQL Server DB

I have a table that has 800K records (it will eventually be increased to ceiling of 3 Mill records). There are no inserts performed on the table, it is for read only purposes.

This is the problem I think I will run into. My hosting company uses MY Little Admin for DB management. When I uploaded the data, I performed a simple query, using myLittleAdmin. No results were ever returned. I assumed that the server timed out before completing the query.

The database contains the names of cities around the world. My question is:

Is there a more efficient way to manage tables this large, and how can queries be performed on this database.

The only queries performed will be to find cities that are within a radius from the longitude and latitude.