I'd say 95 either way. OBD-1 native is much nicer... 96 and up will have as mentioned both higher maint., harder reprogramming, and tougher inspection standards (many states now plug directly into the PCM for 96 and newer cars).
Course, even with a real SS I'd say 95. The 96 cluster in an SS sucks since you lose gauges... with a 95 you can easily swap a Z28 dash in which beats anything ever put in Impalas. Floor shifter can go in pretty easy too. 95s also had hardened pushrods, 96s don't.