Toroidal.
Bear with me here. This is going to take some explanation, but maybe I can explain myself.
Shokhet and Cort Ammon solved the problem of making sure that the station spins properly. A cylinder is probably the simplest solution to that problem, because it's easy to build and maintain. The problem, though, is that it soon becomes hard to get from one end to the other. As you mentioned, Cort Ammon,
As the station gets bigger, and transit becomes more of an issue[.]
This is going to be a huge problem if you want to make a city. You could make a disk-shaped station (to save the rotational aspect and thus gravity, while making it easier to get from one spot to another), but this still requires the station to be large. It'll look like a giant pancake. Eventually, you're going to want to extrude it into a cylinder.
My solution (independent of Shokhet's suggestion, and implemented completely differently) is to create a toroidal space station. This essentially takes Skohet's and Cort Ammon's cylinders and bends them around so the ends meet. Voila! You can get around easily. The reason that toroidal space stations are so popular, as Shokhet said, is that you can rotate them along an axis going through the open center of the torus. My idea is a bit different.
The cross-section of a torus is a circle. You can form a torus pretty easily by graphing a circle on the Cartesian plane and rotating it about some line (you can calculate its properties using calculus). The point, though, is that you can break up a torus into a series of circles. This can be exploited to generate artificial gravity. Instead of rotating the entire space station along one axis, I would rotate lots of smaller circular segments along an axis going through the center of each segment. This would create artificial gravity along all sides of the torus. Rotating a torus about its center wouldn't create this effect, because the "top" and "bottom" would not be effected. The advantage of this design is that it creates artificial gravity along all parts of the surface - which is necessary to fit everyone into a city-sized space station!
The idea has its plusses and minuses, of course.
Pros:
- Artificial gravity wherever you like. I'm really pushing this point, but there's another upside: You could rotate each segment at different rate, providing different gravities (or no gravity at all). Think about how useful this would be for a space station containing many different alien races. Each one is accustomed to a planet with a different gravitational field. If you have a space station with one strength of artificial gravity, most would be unhappy. Here, this is fixed. Note: You could break up a cylindrical station just as easily.
- You can get just about anywhere pretty easily. Part of my motivation for this configuration was that you can't easily get from a point on one end of a cylindrical space station to another. This could of course be solved by planning - that is, designing the station such that people on one end won't need to go to the other. But it's probably best to make all areas equally accessible. On this station, all you have to do to get form one point to another is to simply travel through the center of each segment. You could also bridge the central gap by creating "bridges" from each segment to another.
- It's compact. Let's say you want to make a cylindrical space station that has a surface are of 10 cubic miles. You also want a radius of half a mile, to make it easy to make the artificial gravity you want. The formula for the surface area of a cylinder is $V=2 \pi r^2 + 2 \pi r h$; some algebra leaves us with $h=\frac{10 - 0.5 \pi}{2 \pi (0.5)}= 2.68$ miles. That's pretty long. A torus with the same area is a bit shorter. The formula for the surface are of a torus is $4 \pi ^2 (Rr)$, where $R$ is the radius of a circle whose circumference equivalent of the height of a cylinder and $r$ is the radius of a circular cross section. This is explained better in this graphic:

$R$ is the radius of the pink circle; $r$ is the radius of the red circle. We set $r$ to 5 and find
$$R=\frac{10}{4 \pi ^2 (0.5)}=1.59$$
The width of a torus is $R+r$, which becomes 2.09 miles, a slight improvement. Note, though, that a sphere would be the shape which is the easiest to travel through.
Cons:
- Not easy to build. It's tough to build a circle or a cylinder because of their curved side(s). This is even harder in the case of a torus, because it has many curved sides. It's highly irregular. Your best bet would be to build it in the segments which will be used to generate artificial gravity.
Frankly, I think the pros outweigh the cons here.
Let me end by addressing some of the specific things you mentioned in your question.
Does it depend on what it's in orbit above (if anything)?
From a logistics standpoint, the answer is yes. You need to re-supply any station that is not self-sufficient. However, this is simply a problem for all of the proposed ideas, not just this one. And it can be avoided by making the station completely self-sufficient. I'm being vague here on purpose, because there are a lot of factors that would go into solving this problem.
In your answer please consider factors that go into both building it and maintaining it. If one is more expensive to build but would be less expensive to maintain, then it's possible that it's still better in the end.
I don't think that there would be a huge change in expense among the different ideas. You need to have $X$ dollars/pesos/pounds/yen/euros to maintain a station of a given surface area. Unfortunately, all of these stations that have artificial gravity need to have the same surface area, so this isn't going to change.
Peteris recently said
Umm, How do you propose to rotate sections of a torus? A torus cannot be made of cylindrical segments without gaps or overlap; in a torus, the "inside" part of each section is narrower than the outside, and can't rotate along the red circle in your drawing.
I completely forgot about explaining this part. My "toroidal" space station wouldn't be a perfect torus. As I said, it would be made of segments. However, I didn't explain that the segments would be closer to cylinders than slices of a torus. Think of small cylindrical pieces connected by wedges. Each piece rotates, creating artificial gravity. The torus isn't perfect; it's an approximation.