Oh, and before I forget--I think Assassins are a great idea, and they can be employed somewhat like spies. That is, they use espionage points and have to park for multiple turns to increase the chance of a mission success. Thus, they can be discovered and thwarted like spies.
What would make Assassins different, and thus worthwhile, is one special ability. One in particular--they should be able to assasinate one Great Person located in a city. This includes GPs simply sleeping in the city, fortified Great Generals, and Super Specialists, perhaps in that order of priority. Or only one of those three catagories if necessary to keep things simple.
In any event, the ability to destroy Great People in one fell blow, coupled with the Spy parameters for mission accomplishment, is really the only justification I can see for an Assassin. Plenty of units can pillage, and the Spy performs city sabotage, so something different must be done.
Another Assassin mission: a change to destroy one population point automatically, as opposed to the slower methods used by the spy. This might seem a bit much, but it sounds consistent to me with the type of abilities affoarded by other special units.
What would be really cool, however, is if the Assassin could destroy Leaders! The way this would work: it would require a high difficulty level, but if it succeeds, it would through the civ into anarchy for several turns. The diplomancy screen would be disable for that civ during this anarchy. Then a new Leader would come to power--either the same one if the Civ is limited to one Leaderhead, or an alternate.
This would have the added benefit of shaking up the game by contending all players against a new personality. Which reminds me, I should mention a Leader Death/ Ascension random event to Solver.
Obviously, the Assassin should be a National Unit, limited to three in play like anything else. Also, because of these murder powers, it should not be able to perform any other kind of missions, like poisoning or building sabotage, for balance reasons.