I used to go into Lincoln sometimes when I lived on the Lincolnshire coast some years ago.
Be prepared for a good steep climb up the main shopping street in the center. The first time I went looking for a restaurant which happened to be located at the top of the hill, I asked a cop (at the bottom) for directions and he said "Just keep going up until you need an oxygen mask....."
http://www.visitlincolnshire.com/exec/103701/1054Midlands or North? It's kind of a no-man's land in some ways. It's not far short of the latitude of Sheffield, which is classed as north, yet it's really not that much farther north than Nottingham, which is midlands.
The entire county of Lincolnshire is a little hard to define in that way: The south of the county borders Norfolk, and is East Anglia. The county extends northward to Grimsby, which is definitely north. The western side borders counties which are variously classed as midlands and north. Take your pick!
Probably the most common designation for the part around Lincoln is East Midlands.