Now you've obviously played the games yourself and probably also checked Wikipedia of the NFS Wikia, but I'm still going to list some things that set High Stakes apart from its predecessor, feel free to take inspiration from or ignore completely.
High Stakes was the first NFS to include damage, and it would actually affect the race, from driving in the dark with broken headlights, to making your car slower and harder to control, the worse the damage got. Although you couldn't actually 'total' your car enough to end the race, at its worst you car would slow down to crawling speed, and you would hear explosions from your damaged engine backfiring.
This was carried over in Porsche Unleashed, but in later games damage would be absent or only visual, until the Shift games, I think.
High Stakes was the first game where you could actually visually customize your cars (albeit limited) in the form of career upgrades: http://nfs.wikia.com/wiki/Need_for_Speed:_High_Stakes/Upgrades
High Stakes definitely had a more European flavour to it. In NFS3 HP, all the tracks were more or less North American (US/Canada) with countryside, desert, forest, and Miami-style city (Atlantica) style tracks.
In HS, some tracks were visibly located in Germany, France and the UK, complete with police forces in the correct liveries and sounds (two-tone sirens) - in the two British tracks (Celtic and Durham), the traffic even drives on the 'other' side of the road.
This trend would continue even more in Porsche Unleashed, which took place entirely in European locations (Normandy, Corsica, Autobahn, etc.)
NFS3 had an option that let you race online via IP connection, but NFS:HS was the first where you could race online via EA's own servers, the EA racing network (this also continued with NFS PU, possibly also HP2, I'm not sure). This boosted the popularity for online racing for NFS games considerably, with communities that focused on online competition as a result. Needforbetterspeed.net was one such a community. When EA racing was discontinued in 2003, devoted fans created their own online matchmaking tool with the IPlounge. THis was also the source for the Stock Pack and Expansion Pack for NFS HS.
A subtle difference between NFS3 and 4: NFS4 would punish you more for cutting corners than NFS3, it seemed. In tracks like Snowy Ridge there are 'curbs' in several corners, that will slow you down slightly if you drive over them. NFS3 is a lot more forgiving in this area.