Figuring out which 9mm is like the torture test we go through on nights when dinner isn't on the table:
"Do you want a waitress? Fast food? Ethnic? Decent burgers? Do you just want to run to the market and pick something up? Domino's?"
You've done some of the work already by eliminating sub-compact firearms, and you state that it should not cost "a small fortune." The conditions that you place on your search aren't absolutely relative, but could be open to interpretation. Flexibility is always your friend.
First off, will you be carrying this concealed on your person, or will it merely be a range and nightstand gun? If it's range and/or stay-at-home, size isn't that much of an issue. For carry, "compact" pistols tend to conceal better, especially those that are "melted" so that sharp edges in their frames and slides are reduced to lessen snagging on clothing while drawing from concealment.
Part of the concealment question is your build. Some people can hide anything. Other people are built so that a bunch of keys looks like a bowling ball in their pocket. Generally speaking, larger people with loose clothing have an easier time.
Another part of the concealment question is magazine capacity. More capacity means less concealment, all other things being equal. If you feel confident with eight rounds, you can have a flatter, more discreet profile. Otherwise, count on a bigger grip circumference. Take into account the fact that any spare magazines that you carry are also part of the bulge issue.
I'm assuming that you're right handed, as is 90% of the population. If not, understand that controls are not universally ambidextrous, and that certain pistols are more left-friendly. Choosing something means picking up a lot of pistols at gun counters, and, ideally, renting, where you can, and shooting a few of them.
Will you want to attach anything? A laser? A light? If so, many modern service pistols already come with a front rail under the barrel -- but you'll have an easier time buying one new, as opposed to used. Two separate points for consideration -- let's break them down.
Lights and lasers on your own turf are more defensible, should you ever need them, and you wind up before a judge. Unfortunately, outside of the house, they might make you look like Charles Bronson. Also, if you carry, lights and lasers require that you either carry them separately -- which is semi-pointless and additional bulge -- or that you get a special holster. There
are lasers that take the place of guide rods, but not for all pistols.
Used pistols are generally quite a bargain, and quite often police turn-ins come in to wholesalers well-equipped, broken-in, not yet shot-out, and usually having been inspected on a yearly basis by armorers. The downside of such an older pistol is generally two-fold: more difficult to use modern gizmos, and cosmetic defects from having been banged around in a patrol environment.
SIG, in fact, has a certified pre-owned program. Also, turned-in, ex-police Smith & Wesson 3rd generation pistols (those with a four-digit model number) are generally sleepers with high functionality, long service life, and very little curb appeal -- and thus, very, very reasonable. Back to SIG -- there have been a ton of ex-German police SIG P225s (P6 in their nomenclature) imported -- good pistol, generally carried a lot and shot very little. Also, ex-police weapons quite often come with night sights, which are indispensable for a carry weapon.
Think about whether or not you're looking for double action only, traditional double action/single action, or a Glock-type trigger. Perhaps a 1911? Also, do you want mostly metal, or mostly polymer? Metal frames tend to transmit recoil so that its perception by the shooter is lessened. Polymer frames, less so -- although they
are lighter in the belt, which is important, especially after eight hours of lugging one around. Your choice of action will be dictated by your comfort level with operating a pistol that has, or hasn't, two trigger modes and the possibility of a decocker. Practice with rentals here is a great help in making an intelligent, informed decision.
Hope that helped -- if it did, it probably introduced more questions at this point, which isn't necessarily bad.
My personal choices? Older, single column: SIG P225 or S&W 39-2. Older, double column: SIG P228 or S&W 6906. Modern: Walther P99/P99c AS.
ETA: One more thing - hammer versus striker fired, and the presence or absence of a second-chance trigger pull. Mr. Richard Feder of Fort Lee, NJ, you ask a lot of questions!