MySQL database for storing city bounding boxes and names
(Not a full answer, but too long for a Comment.)

With 200 cities with 'retangular' bounding boxes, virtually anything will do.  Even a simple table without a SPATIAL index, but with INDEX(latitude), INDEX(longitude).

3 million cities, on the other hand, needs some serious indexing.  SPATIAL, as you are asking about, is probably the 'right' way to do it.

Here is an efficient way to do it without SPATIAL, using PARTITIONing and special code instead.  (However, the code given is aimed at a different problem, so it is not directly applicable.)