Question
Origins of God names - Lord Siva and Lord Vishnu
Answer
Shiva
Shiva got most of his major names at birth, as I discuss in this answer. When Shiva was born, he immediately started to cry, and Brahma gave him numerous names to calm him down, as described in the Shatapatha Brahmana of the Yajur Veda:
[Brahma] said to him, 'My boy, why criest thou, when thou art born out of labour and trouble?' He said, 'Nay, but I am not freed from (guarded against) evil; I have no name given me: give me a name!' Hence one should give a name to the boy that is born, for thereby one frees him from evil;--even a second, even a third (name), for thereby one frees him from evil time after time.
He said to him, 'Thou art Rudra' And because he gave him that name, Agni became suchlike (or, that form), for Rudra is Agni: because he cried (rud) therefore he is Rudra. He said, 'Surely, I am mightier than that: give me yet a name!'
He said to him, 'Thou art Sarva.' And because he gave the him that name, the waters became suchlike, for Sarva is the waters, inasmuch as from the water everything (sarva) here is produced. He said, 'Surely, I am mightier than that: give me yet a name!'
He said to him, 'Thou art Pasupati.' And because he gave him that name, the plants became suchlike, for Pasupati is the plants: hence when cattle (pasu) get plants, then they play the master 3 (patîy). He said, 'Surely, I am mightier than that: give me yet a name!'
He said to him, 'Thou art Ugra.' And because he gave him that name, Vâyu (the wind) became suchlike, for Ugra is Vâyu: hence when it blows strongly, they say 'Ugra is blowing.' He said, 'Surely, I am mightier than that: give me yet a name!'
He said to him, 'Thou art Asani.' And because he gave him that name, the lightning became suchlike, for Asani is the lightning: hence they say of him whom the lightning strikes, 'Asani has smitten him.' He said, 'Surely, I am mightier than that: give me yet a name!'
He said to him, 'Thou art Bhava.' And because he gave him that name, Parganya (the rain-god) became suchlike; for Bhava is Parganya, since everything here comes (bhavati) from the rain-cloud. He said, 'Surely, I am mightier than that: give me yet a name!'.
He said to him, 'Thou art Mahân Devah (the Great God).' And because he gave him that name, the moon became suchlike, for the moon is Pragâpati, and Pragâpati is the Great God. He said, 'Surely, I am mightier than that: give me yet a name!'
He said to him, 'Thou art Îsâna (the Ruler).' And because he gave him that name, the Sun became suchlike, for Îsâna is the Sun, since the Sun rules over this All. He said, 'So great indeed I am: give me no other name after that!'
Now this doesn't mention the name Shiva, but when the same story is told in this chapter of the Srimad Bhagavatam, the name Shiva is included:
There was much anger generated in the mind of Brahmā, which he tried to control and not express. Although he tried to curb his anger, it came out from between his eyebrows, and a child mixed blue and red was immediately generated. After his birth he began to cry: O destiny maker, teacher of the universe, kindly designate my name and place. The all-powerful Brahmā, who was born from the lotus flower, pacified the boy with gentle words, accepting his request, and said: Do not cry. I shall certainly do as you desire. Thereafter Brahmā said: O chief of the demigods, you shall be called by the name Rudra by all people because you have so anxiously cried. My dear boy, I have already selected the following places for your residence: the heart, the senses, the air of life, the sky, the air, the fire, the water, the earth, the sun, the moon and austerity.... My dear boy Rudra, you have eleven other names: Manyu, Manu, Mahinasa, Mahān, Śiva, Ṛtadhvaja, Ugraretā, Bhava, Kāla, Vāmadeva and Dhṛtavrata.
Vishnu
Now as far as Vishnu goes, his names have been given all sorts of mystical meanings, but the meanings don't necessarily reflect the origins of the names. The name Vishnu, itself, means the one who pervades. But there are lots of gods who are omnipresent and thus pervade the universe. So why is Vishnu alone called the pervader? It's because "Vishnu" was originally a name of Vishnu's incarnation Vamana the dwarf, because he grew large enough that he pervaded the whole Universe. That is why Krishna says this in the Bhagavad Gita:
Of the Ādityas I am Viṣṇu, of lights I am the radiant sun, of the Maruts I am Marīci, and among the stars I am the moon.
It might seem strange to call Vishnu an Aditya or son of Aditi, especially since Vishnu is unborn and without beginning as I discuss in this answer. But this is actually a reference to Vamana, who happens to be the youngest son of Kashyap and Aditi. In any case, since Vamana was called Vishnu, that became a name of the god that Vamana was an incarnation of.
Similarly, Narayana means "the one who resides in the water", which is certainly an accurate description of Vishnu (except he resides in milk, not water), but it originated as the name of the sage Narayana, an incarnation of Vishnu who was the son of Yama god of death and twin brother of the sage Nara. (Nara and Narayana were the previous births of Arjuna and Krishna respectively.) So people started calling Vishnu by the name Narayana because that was the name of his famous incarnation. And sage Narayana really was a famous incarnation of Vishnu in ancient times, which is why the Mahabharata opens with "Om! Having bowed down to Narayana and Nara, the most exalted male being, and also to the goddess Saraswati, must the word Jaya be uttered."
Note: “The question: Origins of God names - Lord Siva and Lord Vishnu” is licensed by Stack Exchange Inc (https://hinduism.stackexchange.com/); user contributions licensed under CC BY-SA.