Lots of fruit trees in the cherry / plum / apple / almond family are fairly safe bets. They've been used for a long time for carving and woodworking. They are moderately hard: more so than the softer hardwoods. Often the grain is pleasantly fine. They are nowhere as hard and tight as the woods most sought by knife geeks, but they are safer and easier to deal with. I do like the look and feel of cherry and persimmon, but they might not be particularly exotic looking. Pecan and pomegranate look interesting.
