It really shouldn't be impossible to make a decent boss for a First Person Shooter game. The bosses I've seen recently (last 3 years) usually relied on a incredibly shitty methods of being hard. A boss should be difficult in a way that is not frustrating. You should feel that if you get a little faster or better at a couple of game skills you will best the boss. You shouldn't have to get lucky and spend the whole boss fight doing something stupid. When you have to "cheat" the game (Like relying on a path finding problem on the boss's part) you aren't having a good game experience. And why do bosses have to be big? Why not have a boss character that is just as hardcore as the player character, with the added advantage being the new weapon in the game, or perhaps a bunch of fodder enemies? You have another soldier who has basically your stats (Health, speed, accuracy, weapon loadout) and then you are putting your game AI against a player's skill. I have played games where the game AI was very impressive, playing the game better than other humans would. An example of this is the marines from Half Life. They'd dodge, run behind corners, flee towards re-inforcements, and avoid going toe-toe against your superior firepower whenever they could. A boss controlled by AI like that but with the firepower to match yours would make an impressive boss.
"But if I wanted to fight a character like me I'd play multiplayer"
Hmmm. Well, I'll just have to come up with a new kind of boss then. Give me some time. I should talk to good old Bezzy and JP about this.