Imagine The Maltese Falcon or The Thin Man set in Regency England, with an Agent of Inquiry (private investigator) named Sarah Tolerance whose mind is as sharp as the sword she wields with expert skill. Miss Tolerance moves from the lowest whore houses of London to the heights of society as she pursues mysteries, solves murders and avoids threats on her life. Point of Honour and Petty Treason are marketed as Regency Romances, but really anyone who likes Dashiell Hammett should enjoy these brilliantly realized detective stories set in a slightly alternate history. They'll also learn some sword play, since Madeleine Robins makes her battles as realistic as everything else about the period. If only they can get Kiera Knightly to play Miss Tolerance in a movie version.
Sharon Lee and Steve Miller write like Andre Norton at the height of her skill as they spin tales with tremendously engaging characters in the Liaden universe. The Partners In Necessity collection contains reprints of the first three books in the Liaden series, Conflict of Honors, Agent of Change, and Carpe Diem.
This is historical fiction, not fantasy or science fiction, but Bloody Jack by L. A. Meyer is just plain bloody fun. The title character is a young orphan in London around 1800 who (in order to keep from dying in all the ways penniless orphans could die back then) disguises herself as a boy and takes the name Jacky to gain a berth on HMS Dolphin. Jacky Faber is a great character, telling her story in her own voice. The author (himself a Navy veteran) has done a fine job of getting the feel of a warship under sail and the life of a sailor. Even though Bloody Jack and its sequels are marketed as Young Adult (teen) books, these are simply good reads for any age, as Jacky bounces from place to place and situation to situation, usually leaving chaos in her wake.
Bud Sparhawk's Sam Boone: Front to Back follows the misadventures of 'Sam Boone, Galactic Hard-luck Case Extraordinaire.' It also contains the infamous 'lost' Sam Boone story in which heavily-armed, warlike aliens get stuck in Disney's Small World ride with unfortunate results.
Kristine Smith's Jani Killian series evokes the life of an undercover operative in a tale in which Jani never really knows who to trust and sometimes can't even tell who she herself really is. This isn't James Bond "Kiss Kiss Bang Bang" fiction, but rather the sort of life and situations real agents might find themselves facing, although with aliens, interstellar travel and genetic engineering to further complicate things.