I've heard that some residency programs (example: Mayo) will help students with travel and motel costs when they come to interview. Is this true, and if so, what other programs do similiar things?

I know mayo provides accomodation, but I don't think they will pay for your traveling costs. Other programs that offer free hotel stays include cincinnnati, cleveland clinic, ucsf, emory, wisconsin, cornell, to name a few. Most programs have contracts with hotels so that you would get a discounted price (though it's probably even cheaper if you bid on priceline.com).