Multiple choices would have been good. I consider the character's alignment, class and race (as a whole, but more or less in that order) and then pick a deity as a further point of definition or difference for the character.
For example, my CG ranger worships Sylvanus in order to make him clearly different from a ranger of Mielikki, since he is much more about supporting the common people and the purity of nature despite its dangers and often cruel indifference, rather than regarding nature as a benevolent or easy protector. My NG dwarven fighter 1/wizard 5 follows Kord in order to represent his background as a wandering sword-crafter for hire who is more at home with human warrior bands and mercenaries than with his own people.
I wrote up a half-elf character who needed at least three deities of very different nature and alignment to describe his attitudes and beliefs. edit: Sorry, four: Torm, Tymora, Mystra and Mask.
I would usually pick a deity for a non-cleric, depending on the character and setting - I don't think atheists are very realistic in most mediaevally-based settings, though they fit well in Planescape - but would consider most non-clerics, even divine casters, as more than a little polytheistic. The ranger would advocate and practice honouring Tymora to gain favour for adventuring pursuits. I like the precedent of Sparhawk and his order as paladins who are explicitly both knights of the Church and followers of the old religion to gain helpful magical powers (sorry, the specific names escape me).