I just installed OSMand to try it out, and it didn't have the street I live on. It also didn't have my place of work on it, although it did have that street at least.
I downloaded the maps for my state. Are there local maps that I would need to download as well?
Open Street Maps have much more users (and thus better ground coverage) in Europe, e.g. Germany. I think that's why the experience may be diametrically different for different people.