on a flush i don't think they change the filter they just hook up tubes and flush the fluid. just check that out and see if they even changed anything. fluid shouldn't smell burnt and should be checked when warm. on an 04 you shouldn't have that many miles on it unless you haul a lot. if you do you should change the fliud & filter every 20-25k. if you have OD off, when towing only, it will shift differently. little bit firmer/stronger like a shift kit. you will also run the gears longer thus the firm shifts. when your coasting or slowing at high speeds with OD off the trans will downshift a little slower and kinda clunk into 3rd. 3rd gear will have the TC lockup on being a 1:1 ratio and applying the torque. don't worry about the clunk from downshifting it's normal.
when your trans acts up is the truck warmed up or is the trans cold?