I loved Tuf Voyaging so much I named one of our cats Havoc. The second one is named Pixel, so you know who else is high on my favorites list.
Med Ship, by Murray Leinster. It’s a collection of stories about a doctor who goes from planet to planet, solving medical mysteries. Frequently politics and war are involved.
Julian May’s The Saga of Pliocene Exile: The Many-Colored Land, The Golden Torc, The Non-Born King, and the Adversary.
I’d like to suggest collections of short stories in general, either by one author (Robert A. Heinlein’s The Past Through Tomorrow; Isaac Asimov’s I, Robot) or groups of them (The Science Fiction Hall of Fame).
Get the Hugo Winners, Volumes I and II. The stories are old, but you can generally pick up a used copy for a song. Then you have a selection of authors to check out. There are also more recent collections of Hugos (a SF award that is voted on by the members of the World Science Fiction Society). I’ve always found the Nebulas (a SF award that’s voted on by the authors) to be far more hit or miss for my own tastes. Some Nebula winners I loved, some I hated. Also, it’s always worthwhile to pick up L. Ron Hubbard’s Writers of the Future. I couldn’t stand Hubbard as a writer, a person, or a cult leader…but he did do one thing that was worthy. He started this contest. Most of the stories in the WotF contests are very, very good.
I’ll profoundly disagree with recommending Asimov and Heinlein for someone like the OP. There’s a reason why Asimov felt such disdain for Le Guin et al ("“I hope that when the New Wave has deposited its froth and receded, the vast and solid shore of science fiction will appear once more.”): he wrote from an entirely different aesthetic than the new-wave authors. Personall I can barely stomach Heinlein and Asimov, and for me they represent some of the worst of the genre. YMMV, of course, but I think the OP is really unlikely to vary that much.
The Sparrow is a great recommendation, on the other hand. And one that hasn’t been suggested yet is Embassytown. It does deal with interstellar space-travel through some hand-wavery. However, it’s got fantastic, fleshed-out characters, it’s got a meeting with a weird alien race, and it’s got social dynamics worthy of Le Guin (who reviewed it for The Guardian).
Niven and Pournelle’s The Mote in God’s Eye is an outstanding first contact story - there’s certainly a military dimension to it (the two human vessels involved are undeniably warships), but the political, diplomatic, scientific and even religious implications of first contact are also well-covered.
xtisme and silenus, I’ve emailed back and forth with Martin now and then over the years, and have strongly encouraged him to tell us more tales of the redoubtable Tuf when he’s done with Westeros. He said he’d like to.
Asimov was not strong on characterization, and (especially at first) could barely write female characters. Yes, yes, Susan Calvin is not a stereotypical woman, but even she melts when she has a child substitute. She turns into a Mommy, and gladly. She can’t help herself. So probably Asimov isn’t the best choice for the OP. Heinlein DOES write some interesting characters, and when he was good, he was very, very good. I think that his juveniles were his best, and he had some pretty good stories for adults, as well. I’m odd, I guess, because I love Asimov AND LeGuin, but for different reasons.
Scalzi’s Old Man’s War and its sequels do portray very ALIEN aliens, as well as very human humans. I’d like to recommend Fuzzy Nation by Scalzi, unless the OP hasn’t read H. Beam Piper’s Fuzzy books yet, because I think that he should read the originals first, and THEN read Scalzi’s reboot.
I’m currently re-reading some of James H. Schmitz’s stories, which are very much character driven. However, Schmitz uses a lot of psi, which the OP might regard as magic, even though it’s couched in scientific terms.
Thanks again. I plan on reading Embassytown first (if it’s good enough for Le Guin, it’s good enough for me) and then I’ll give Starship Troopers a try. I have read some Asimov, I found his characters too wooden, but 2001 is one of my favorite movies FWIW.
A pun on the flat Mesklinites, right? 
Although I like the books, they really have most of the stuff that the OP doesn’t want:
- Aiken and Felice act like petulant teenagers; it’s their main character trait.
- Metapsychic powers of the Tanu and Firvulang are portrayed as a magic stand-in.
- The Tanu and Firvulang aliens are so similar to humans that the Tanu are using humans as breeding stock.
- There’s just not too much humor in the books.
They books certainly aren’t focused on the science to the exclusion of plot, so there’s that.
I LOVED Eifelheim. It’s not quite like anything else I read, and I really enjoyed it. I’ve been trying to read Flynn’s The January Dancer. It started off well, but after a few chapters I’m having trouble staying interested. 
Blindsight was another novel with genuinely creepy aliens. It also brought home to me the sense that space is Big. Really Big. And we’re not very important in the grand scheme of things.
I like Peter Watts, but he does have kind of a dark vision.
Update: I think I’m going to read Embassy Town and The Sparrow, they both sound like exactly what I’m looking for. Thanks for the suggestions and I’ll keep checking back to see what else looks interesting.
I love Asimov and Heinlein myself, but yeah, given that the OP requested character-driven fiction, I am totally surprised people were recommending Asimov, Clarke, and Heinlein. (And I wouldn’t call Heinlein misogynistic, exactly – he does have some pretty cool women characters, like Wyoh – but he sure does have some weird attitudes towards women.) The only exception is The Moon is a Harsh Mistress, which I do think is a great book.
Another vote for Bujold, who has interesting science <i>and</i> interesting characters and humor and basically is everything you could ever want. I also like the Octavia Butler Xenogenesis books recommended upthread – the aliens are, per the OP request, really alien. (The technology is a bit magic, though – but what would you expect from super-alien technology?) Also, the James Tiptree, Jr. short stories hold up well.