First thing I'd do is swap the new tires from side to side. Although a bad
tire will usually demonstrate itself all the time and not just during
braking, it is possible.  If that proves nothing, then it IS possible you
have a bad hose, AND it's possible they caused it by letting the caliper
hang by the hose.  If that's the case I imagine you're going to get to pay
for it.  You'll never prove they did it.  Another possibility is that the
calipers need to be replaced and the piston was fine with worn pads, after
they pushed it to the bottom of the bore, it becomes sticky. One last thing,
is the caliper slides themselves, they need to be very free, and well lubed,
allowing the caliper to float properly.

Sounds like they screwd up the Alignment. Happend to me once at Pep Boys on
my Camry, then I took it to the Toyota dealer and had them redo the
alighment and have not had trouble since.