Short of putting a gauge in line and giving me line pressures at shift points, my guess from what you are telling me is that your line pressures from your valve body are just a tad bit high. Your torque converter does not lock up until after you are in 4th; generally at 47.5 mph at a "no load" situation.
The clunk really isn't bad, but can be hard on U joints and annoying. Line pressures can be lowered to give a smoother shift, but that will greatly reduce the life expectancy of your transmission clutches because it will slip them more between shifts. Your fluid does not need to be changed.
Believe it or not, many people report good results by adding Lucas transmission addative to their transmissions that is formulated for exactly the symptoms you describe. If you have an AutoZone or similar store, look in the transmission addative section for Lucas bottles. Once you see the bottles, read what they say and you'll see one that says it corrects exactly what you describe; hard shifts. I'm normally not big on addatives, but GM, and Dodge both have their own addative for limited slip rear differentials that are basically the same thing that this Lucas stuff is. I've seen some GM and Dodge pickups chatter the rear wheels really bad going around corners and the dealerships just add a bottle of the factory addative and drive them for about 50 miles and the wicked chatter goes away. People have reported to me that the Lucas has done the same with hard clunking shifts in transmissions.
Good luck.