A 4l80E would be the way to go if you want overdrive. However it will not be a cheap swap compared to throwing in a TH400. Like HO455 and others have said you will need a stand alone controller. These range from $500-$1000 bucks. You will also need a throttle position sensor. This is 100-$150. IIRC the 4l80 is longer than a TH400 so driveshaft mods are in order. Approx $100-$150 bucks here. You will also need to convert your speedo or buy a aftermarket one $100-$200?
Or drive by GPS. Now you still need to buy the transmission. Prices here range wildly. You could buy a good running donor rig and part it out and end up with a free transmission. Or you can buy a rebuilt unit anywhere from $1000 to $2500.
Any transmission purchased used I would consider a core unless you can drive it or get a warranty from a salvage yard.
At the end of the day the TH400 starts to look mighty good.
Just my opinion.