Thanks again for your thoughts, Dan. I took this to some of my Esri friends from the Spatial Analyst team at Esri UC and they had the answer for me right away: when you are calculating costs, you need to calculate the cost per map unit, not per cell. In retrospect this makes a lot of sense as the result is not dependent on cell size!
In my case I came up with the following equation to convert miles per hour travel time (on vector data like roads) to cost in minutes per foot (ie map units, I'm in state plane):
# conv factor: 60 min/hr / 5280 ft/mi = .00136 min-mi / ft-hr
# cost = .00136 min-mi/ft-hr / xx mi-hr = yy min/ft
My results now look like what I was looking for with travel time in minutes on my map (I assigned a slow mph to overland travel cells):