I have to come up with a new naming convention besides "Level X Terrors", but regardless, let's go over some of the scariest level 3 monsters in the game that don't see as much use as the standard goblins, orcs, and gnolls.
The Gnome Arcanist is a very devious controller that resides on page 134 of the Monster Manual. The reason this monster is so cool is that he has a lot of abilities to get away from melee attackers, even fighters who are very hard to escape from once they mark you.
The attack you are probably going to use with them most is Scintillating Bolt, which deals 1d6+4 radiant damage and causes the target to become dazed until they make a save. They also get a minor action ranged attack that slides a target one square. Make use of this every turn if possible sliding targets back that may be able to reach you on the following turn. If targets do close into melee the Gnome Arcanist can use Illusory Terrain, a close blast 5 that hits only enemies and slows them (save ends). If that doesn't make it easy enough to get away, they can teleport 5 squares as a move action once per encounter, and if they do get hit they turn invisible until they attack or until the end of its next turn.
If you can draw a melee character into chasing after you then you can have a lot of fun with this monster, running about the room, slowing and dazing your would be killers and teleporting or becoming invisible if need be. If you want to make a really memorable bad guy consider combining this guy with a Warlock or Wizard template, and play up his trickster nature with a bit of roleplaying. This would definitely be the kind of villain that taunts your players while he fights them.
Darkness is a really under-utilized element for most DMs and can be a great obstacle for PCs to overcome during certain encounters. On low levels one of the best options is the Shadowhunter Bat. It deals 1d6+4 damage, but that rises to 1d6+10 if they are in dim light or darkness, and they get a +2 to their attack rolls for it as well. They have perception +7 as a skill, so they might actually notice a rogue attempting to sneak up on them, and they can fly at speed 8, darting out of your melee character's reach, causing them to ready actions in order to really hit them in most cases.
They also get flyby attack, which they can do as often as they want. It allows them to move 8 squares and make an attack at any point during the movement. The bat doesn't provoke opportunity attacks when moving away from the target of the attack. Combine this with their stealth +10 and you can have a very deadly surprise round set up for your PCs.
Shadowhunter Bats are on page 27 of the Monster Manual.
Young Brown Dragon
The first solo monster I have used here is indeed a dragon, but probably not the most used variety. The Young Brown Dragon is a very challenging encounter for most groups, but it is definitely more memorable than the other young dragons, and has cooler abilities to make the fight more fun for you as well. You can find the monster's stat block on page 168 of the Draconomicon.
First off is the dragon's mobility. He has an 8 speed, plus he can fly at 6 speed and burrow at 6 speed. Definitely try to make use of all of these if you really want the players to remember the fight. Don't just have him sit in the middle of the room blasting away with his breath weapon. His basic attack is either his bite, or his claw attack, both of which are reach and vs. AC, though the bite does 1d8+4 where as the claw only deals 1d6+4. The Dragon also has double attack though, allowing him to make two claw attacks with a single standard action, and the dragon also deals 1d6 extra damage if he has combat advantage.
My favorite ability the dragon has is Sand Spray. Its an immediate reaction that is triggered by an enemy attacking him with a ranged attack. It deals 1d6+1 damage and blinds them until the end of the dragon's next turn. Being blinded also means that he has combat advantage, so this would be a perfect time for the dragon to burrow or fly over to the target and deal a lot of damage to him.
The Brown Dragon's breath weapon is a little different from most others. It is a close blast 5 that remains in place until the end of the dragon's next turn. Any creature that starts its turn adjacent to the area or that moves through the area takes 5 damage and it blocks line of sight for all creatures except the dragon. As with most dragons he automatically recharges and uses it when bloodied. You can use this line of sight block to stealth and become hidden, gaining combat advantage for surprise attack.
Also like most other dragons, the Young Brown Dragon has Frightful Presence, which stuns enemies in close burst 5. Even after the stun wears off, it leaves an aftereffect that gives its targets -2 to attacks until they save. Using this ability early in an encounter will help keep your dragon alive and dealing damage for as long as possible.
The Brown Dragon also has a move action attack called Sandd Cloud. It turns into a cloud of sand and can move a number of squares up to its speed, including moving through enemy's squares. When it does so it deals 1d6+4 damage and blinds any creature who's space it enters. The blind is also save ends. So as you can see its plenty easy to get combat advantage and deal a lot of extra damage with this beast.
The key to this fight is to make sure to roll your recharges for abilities, and to use Sand Cloud and Sand Spray as often as possible, then taking advantage of the combat advantage once you have it. With a monster this sneaky and resourceful, you might consider not using its action point right away, waiting until it has combat advantage so it can pounce on a target with 4 claw attacks, each with combat advantage.