Yes, a bump map would work, or a displacement map would work, although there's limitations on both. Bump maps aren't affected at all by raytracing (its in some ways more along the lines of a post-render effect) so there wouldn't be shadows inside the emboss. For displacement maps... I personally have yet to find a way to get displacement maps to go in - they seem to bump things out for me.

As for your boolean problems... If all you extruded were edges, that could be your biggest problem. if you tried to boolean a section that was just an open border of edges, the program can't tell which way is in or out. That could be problem number one, although I can't really tell without a slightly more accurate account of what you're doing. If you can close those faces, your problem might be solved.
In any case you may want to hit polygons>cleanup to make sure nothing funny is happening....

Oh, and as of (at least) maya 6.5 and later, maya has a text function (where you can type in text and it spits out a geometry version of it; see create>text). If all you need is embossing of actual text, you should be able to get words and letters (ready for booleaning, I suspect) from there.