Most effective use of DB querys

The $wpdb object is based on ezSQL, it does not add much overhead, so I would not worry about that. Opening a second connection to the database yourself will probably lead to more overhead than using the $wpdb functions.

The three queries you have described are ideal queries to do in the database (a small result set from a large dataset), so you should not emulate them in PHP. Be sure to add some indexes to the table to speed the queries up (one on city at least). Use the EXPLAIN feature of MySQL to know what the database is doing to execute your query and how you can help it.