How can I calculate the average latitudinal temperature anomaly between a city and all other locations along the city's latitude?
I think you'd be looking for a gridded dataset, where data has been interpolated to a grid of the Earth, rather than one that has data at particular points (eg. stations). I'm probably not the best person to recommend one particular gridded set over another, but a good start might be the Met Office's HadCRUT4 set, which combines gridded surface temperature data over both land and sea.

I haven't looked at HadCRUT4, but I daresay it'll come (either in plain text or NetCDF format) as a lat/lon/time array (grid), and if you're interested in a particular latitude, you should just be able to read off a latitudinal row. Then you can look at it however you like: subtract the temperature of the point closest to your city from the rest to get an anomaly right across the latitude, or average the whole thing (a zonal average) and subtract the city baseline from that. Hope that helps :)

Edit: HadCRUT4 is a monthly dataset. If you're looking for more temporal resolution (the weather tag suggests to me that you are), I'm not sure what availability among gridded sets is like, but you could try taking a station set (eg. HadISD, which is hourly) and gridding it yourself.