As you've discovered, Latitude/Longitude coordinates have issues on a 2-D map. Every mapping projection does, but LL has particular issues given that your coordinates aren't the same size everywhere. The width of a degree of longitude isn't the same at the top of the US as it is at the bottom, and that distortion makes coordinates hard even before the stretching issues. Luckily, there are a lot of people (like myself) who have to work with maps for a living, and lots of solutions to the problem. And all of them just use math.
For what you're doing, your slice method is an excellent solution; cutting a large map into smaller pieces 'relieves' the distortion as you move further and further from an origin (one of your furthest corners). The usual convention for coordinate systems is to set your origin to some furthest SW corner well outside your map, so that all mapped coordinates are +X and +Y, or in this case +E and +N. You'll see these referenced in systems as "Northings and Eastings", and they have the additional advantage that they are always in feet or meters, so they are always the same size regardless of where on your map you move. Different of these systems cut maps up differently (California State Plane is divided into 6 zones N to S, Oregon State Plane into 2) but for a US map what you've created is basically a version of the Universal Transverse Mercator system.
UTM cuts the earth into pole-to-pole slices along certain lines of longitude, each one referred to as a "zone". For the US, we use zones 10 through 19, as shown in the following randomly chosen google image search result: http://www.wa6otp.com/fig44.gif. Each zone has an origin well outside the US, and all points are mapped as +N and +E. As you move across the country you switch from one zone to the next.
Implementing this is a pile of trig (again, a dart thrown at google "convert LL to UTM formula" reveals the following which has more explanation than you need: https://www.uwgb.edu/dutchs/UsefulData/UTMFormulas.HTM ) but if you do you can just throw LL values into your program for every city you decide to use, and it'll plot them accurately on your map without you having to reinvent the wheel. Note also that the above link goes into a lot of talk about Datums and Ellipsoids, which is a whole other kettle of fish that I will restrain myself from explaining no matter how cool it is to understand the problem they're solving. I'm a geologist, what can I say, I get into this stuff. If you go this route, you want everything you do to say "NAD83/WGS84" (either/both is fine) as that is A. the most commonly used system in the US, and B. the system Google Maps and Wikipedia both use for their coordinate data.
I hope this ends up being useful to you, even if it's just to give you a framework for how to approach these problems.