Xi Tiger and Seven Force
It was hard for me to choose just one boss from this game, so... I picked two.
In what little story there is within the actual game cartridge, Xi Tiger is definitely one of the two major villains mentioned. He basically murdered a little girl that triggered a change in a boy that became Epsilon Eagle, and then becomes the main target for the first ten levels of the game. He confronts Epsilon on top of a moving train, looking fairly creepy starting out as a humanoid guy with claws, but then undergoes a transformation into a massive clawed alien tiger. What follows is a rather intense battle considering he has only melee attacks. A seasoned player who mastered the teleporting dash wouldn't have much of a problem, but anyone without an understanding of it will be promptly murdered by Xi Tiger's enormous reach.
Seven Force's story in the game isn't very much explained, but speculation is that she is the murdered girl brought back to life as a partially robotic super soldier. Seven Force is a reference to a transforming robot from Gunstar Heroes with the same name. Alien Solider IS linked to Gunstar in a number of ways, almost a spiritual sequel. Seven Force in this version can (unfortunately) only take five forms, but each one is tremendously difficult in its own way. What's worse is that certain forms are immune from certain ammunition, so you need to make sure to have a variety of weapons in your arsenal. A cool tidbit is the fact that each force is named after a mythological woman of some kind (Valkyrie, Medusa, Sylpheed (Is that mythological? It might not be), Artemis and Sirene).