I travel for work quite often and I am always looking for pet friendly places so that the kids can go.
They don't advertise it, but Drury Inns are totally pet friendly. You have to sign a letter agreeing to the rules - which are reasonable - but no extra charges or deposits are required.
LaQuinta is also pet friendly. I know there are others, but these are the ones I find most available.