I agree with both that a deity would welcome the worship of any being, and that you could not sincerely worship a deity and remain of a contrary alignment for long.
As for your character, Nuetral Good is diametrically opposed to Nuetral Evil. Therefore, I would argue that Lawful Good is actually closer to Shar's tenants than NG, if only because LG doesn't make much since in terms of a NE philosophy, were as NG is more clearly its opposite. Despite the fact that Shar would love to attract LG followers, I don't think that many people who were LG would be attracted to the worship of Shar. What about the philosophy of Shar attracts the character? Why is the character tempted to 'fall'? I certainly think that if a LG person were to worship Shar sincerely, that there alignment would immediately convert - probably either to LE or N if not NE directly.
As to the alignments of the followers of a diety, for the most part any dieties worshipers are probably Nuetral, and there are probably factions of followers up to two alignments removed from a given diety. However, most worshipers will probably be somewhat casual in thier worship, and their devotion is of the sort motivated by what they percieve that they can get in return for the worship as opposed to love or high regard for the principles of the diety. The pious, sincere, core believers are probably the same alignment as the clerics. So Shar probably attracts largely N, NE, LE and CE followers, with a smattering of LN and CN's.