Great topic, thanks for posting.
I have known cyclist friends who have often been frustrated by bicycle maps; it seems a lot of times they are either complaining about them being too hard to read (showing too much detail and/or a difficult to read color scheme) or not having enough information (such as a regional map not showing enough local roads).
The incorporation of local knowledge is important as well. I've heard of organizations doing studies on where people actually choose to ride in relationship to where an officially designated bicycle route is. Portland comes to mind where the majority of bicycle routes are on local/residential roads, which makes them pleasant to ride on but perhaps not always the most direct option. Many of the arterial roads in Portland are not bicycle friendly though cyclists may prefer them over cycling routes for the direct commute. Having been an urban cyclist for the past 13 years, and a bicycle messenger for 3 of those, I have done my fair share of cycling on the worst roads one could possibly imagine for a bicyclist (I even was kicked off a freeway once in Spain). If such a road or route exists not as an "official cycling route" should it be represented on a map as well?
Another design challenge that comes to mind which I haven't seen discussed yet in this thread is the map's physical size. The Adventure Cycling Association not only does a remarkable job at designing cycling maps, but their maps' size conforms to fit inside a handle bar bag. This works because each of their maps are created for a specific route and don't show much area off the route, so this probably wouldn't work well for an entire urban area. One solution to this I've considered is creating a "London UnderGround" type of bicycle map that would serve as a quick overview of which routes connect to which points of interest and neighborhoods, thereby diliberately choosing to not adhere to a traditional map scheme but utilizing more of an info graphic convention. Such a map could fit in a pocket or handlebar bag and serve as a reference rather than a highly detailed DOT or USGS topo style map. Detailed regional maps are great for planning a trip, but not easy to glance at while on the road.
Never have I tried using my smart phone as a navigational tool when riding, though I have seen them mounted on handle bars by some cyclists to be used as a GPS. The advantage of planning a route and generating a "cue sheet" (list of directions with mileage and turns) that could be toggled from the map view would be very helpful with such a set up.
Finally, having lived in the San Francisco Bay Area for the past 5 years until recently moving to NYC, I've found many people to be partial to the East Bay Bicycle Coalition's maps: https://www.ebbc.org/maps
Just my thoughts and Mike your Central Minneapolis Bikeway System map is excellent; I approve of the greyed out background information that has been appropriately generalized while having the cycling routes stand out through the use of highly saturated colors. This makes the map very easy to read and understand. Nice work!