Here's a graphical enhancement mod for AvP:
http://www.moddb.com/mods/aliens-versus-predator-classic-redux/downloads/avp-classic-redux-20-part-1-of-2
http://www.moddb.com/mods/aliens-versus-predator-classic-redux/downloads/avp-classic-redux-20-part-2-of-2

To install, first run AvP once. Then just extract and copy the files into the main AvP directory. I've tested it on singleplayer and it looks much better.

Here's some before and after pictures:
http://imgur.com/a/Nkckx

About the "Level" pictures:
Are you seriously standing in the same position?
- The bed looks different
- The floor looks different
- The wall with the screen looks different
- The wall behind the table looks different
- HUD Element left bottom looks different
And I don't mean higher resolution, but CHANGED.
Also, I like the colors of the old menu better.
I think I'll skip that mod.

Here's a better set of screenshots standing in the same place:
http://imgur.com/a/Nkckx

And yes some textures seem to be changed more than others because I'm guessing textures were not remade at a higher resolution, appropriate alternatives were found in order to mimic the movies.

You do need both parts of the mod installed or bad things happen. The worst you can do is deviate from the written directions.

Look at everything from the main page first. There's tons of screenshots and more downloads. GeneralLotz made a cool walkthrough, too. I also highly recommend the Predator Plasma Burner and SADAR Mk2 addons as well as the extra maps for the complete experience.

Thanks for the info!
I updated the OP with some changes.

No problem. I still get emails about invisible body parts and all sorts of weirdness because the 2 downloads and new "graphics" folder can throw people off.

Oh yeah, AvP Classic supports ENBSeries and SweetFX if people want to push the game/mod further.

Looks nice with Redux Mod, Graphics folder is a little confusing as it doesn't actually say what to do with it. Mind you just dropped it in the folder and it's working fine so guess all the dll etc tell the game to look in that folder for textures etc.

I was looking for the folders within graphics initially but not seeing them led me to the above.

Added the original Predator intro and now just need to change the menu background and completely sorted, may grab a few of the weapon mods also like original smartgun etc

Would having this mod installed cause any problems with the online component GOG is currently testing for Galaxy?

It should be compatible with people who don't have the mod but it seems GOG Galaxy is verifying the files and replacing them with the original ones. http://www.gog.com/forum/aliens_versus_predator_classic_2000/mods_being_disabled_by_launcher

It would be nice to get a blue post response to this.

Yeah that would be nice.

I installed the Redux mod, works perfectly - but I run the game directly from the game .exe and not GoG launcher (Galaxy)

I really recommend this mod, it has a lot of heart in it and makes AvP just a little bit "fresh" :)

It's 3GBs of textures and maps, making the game look a whole lot better.

Where does the graphics folder go? How do you install that correctly?

Place it in the folder called AvP Classic. It doesn't need to go into any subfolder.

The page says some of the missions have been changed but it doesn't mention AI as far as I can see

No, this mod doesn't change the AI in any way. The game's AI isn't the greatest; it is 16 years old after all.