Here are two other techniques I look forward to trying with my GF: TSP (Traveling Salesman Problem (yes, really!)) and Stippling. Both techniques are useful for devices such as laser cutters, as they don’t depend on true greyscales.
In case you’re not familiar with these, here are a couple of examples:
First the Mona Lisa rendered as TSP:
And here’s a nice example of Stippling:
The good folks over at Evil Mad Scientists have put together some tools and a tutorial for these methods: http://wiki.evilmadscientist.com/TSP_art & http://wiki.evilmadscientist.com/StippleGen respectively.
NB: The techniques involved require at least a passing knowledge of image manipulation and depend on user-installed programs, so I’d say these might be intermediate-level projects if one has never worked with them. YMMV, of course!