I suppose you considered using the cnc to cut a mold - then cast the letters? I ask, as that opens a new set of questions for materials -- as opposed to milling them out of a plastics. Then you'd be into paint and finish too
They could be cast in any number of resins, solid or hand lay-up as hollow backs with mounts cast in. Justa sideways view you might consider. An added advantage - you'd probably store the molds for replacement when they go "walkabout."
There are some really awesome cast resin products coming outta China that are extremely detailed and highly polished. Not you'd choose that - just an example of the material processes.