When I was driving around Maine I never saw a billboard (I assume banned) but they had little signs a bit bigger than a regular road-name sign that indicated in which direction various kinds of shops and restaurants would be with distances. Like a sign might point right and say "McDonald's 0.5 Miles ==>".

It wasn't necessarily as good as a giant golden M visible from a mile or more away, but it was sufficient. I think the logo signs + small directional signs once you're off the highway would do a good job in most areas. Plus once you're on the main drags that hold most of these things you'll be hard pressed to miss them. It didn't take long to get used to looking for them when driving around either.