Lone Wolf and Cub is definitely worth looking into. It’s monstrously huge, (28 volumes at 10 bucks each is kind of a lot) but it’s fairly episodic, so you can pick it up slowly. And it’s one of those pleasant instances where something was both spectacularly influential and very well done in its own right.
Blade of the Immortal is also really good. The art’s spectacular, and the emotional storytelling is strong, too. Plot’s a bit slow, but you can’t have everything. The layouts surprisingly ‘dense’ for a manga, which almost makes it look like an American comic.
Both are wandering samurai stories, so you’ll need a very high tolerance for blood and a reasonable tolerance for women being degraded, though. LWaC is written well enough that its occasional dips into 70’s style exploitation can be pretty easily forgiven, though. And BotI behaves itself most of the time.
It’s probably a bit hard to find now, but I really enjoyed Sanctuary, a yakuza/political series that had a very strong plot. Banana Fish another mostly yakuza series started off pretty good, but I lost track of it after a fairly short time, so I don’t know how it went from there.
Battle Angel Alita starts off very strong, but the quality goes downhill fairly fast. You can probably drop it after the third or fourth graphic novel with no real loss. The manga version of Maison Ikkoku as mentioned, was a lot of fun as well.
3x3 Eyes was just re-released, wasn’t it? Fairly light anime-ish horror, but a lot of fun. I’m blanking on other SF or fantasy manga for some reason, though I’m sure a Shiro fan will show up sooner or later and threaten you with horrible fiery death if you don’t read Appleseed.
Gold Digger is worth looking into, too. It’s might technically not be manga (It’s produced in NA and written and drawn by an American) but it’s close enough. A very enjoyable exploration of pretty much all things geeky, and gets everything manga does right, right, without feeling like a knock-off.
I’m enjoying the Love Hina manga hugely (much more so than the anime, in fact) but I’m not sure it’d be a good place to start. LH is basically a big sloppy love letter to shonen manga in general. Sort of a manga loaf, made of bits and pieces of other beloved series, chunked and formed.
Which Vampire Hunter D? The good one, or the one that just came out? 
–
Now if only someone’d pick up the rights to Berserk . . .