Heather,
Actually a 9-10mm, AAA grade Black Freshwater is a great alternative to a strand of Tahitians. This size would be considered a "small" Tahitian but is is a very popular size. However, Black Freshwater pearls would cost about 1/10 the price of the Tahitians.
The coloring process is perminant and I would not focus to heavily that they are died since almost all pearls are treated in some fasion after harvest. Make sure that in the 9-10mm range that you look for AAA grade. This grade will have a very high luster and a very smooth surface.