Vedas say time is cyclic. So, there is no first creation.
Even we can comprehend it logically. If we assume there was first creation of Universe and other living beings (jivas), why some Atmans aquired status of Devas and why some Atmans took birth as humans and Rakshasas during very first birth? Even in Humans, why some Atmans were born as Brahmanas and why some Atmans were Sudras for the first time? This selection can't be random as it violates Law of Karma of Vedas. So, there must be no first birth or first creation to apply law of Karma properly. Our Atman and Supreme Brahman are eternal and Universe is undergoing creation, preservation and destruction since eternity.
In the book Spiritual heritage of India, Swami Prabhavananda says
To the Hindu, creation is beginningless and endless. That it is
beginningless he proves by a simple process of logic. If creation had
a beginning, then must the creator also have had a beginning, since
until there is a creation there can be no creator; but to admit that
the creator had a beginning would be to admit that God had a
beginning, since God is not God until he creates—and to think of God
as having had a beginning would, to the Hindu, be a manifest
absurdity. God, who contains within himself the seed, the material
cause, of the universe, first brings forth the universe out of his own
being, and then in due time takes it back again to himself. This
process of creation and dissolution goes on for ever and ever, for it
is as endless as it is beginningless. Eternity is witness, not of one
universe only—that, for example, of which we are now a part—but of an
infinite succession of universes. The birth, life, and destruction of
a universe constitutes a cycle. To say that there was never a first
cycle, and will never be a last, is only a way of affirming that the
creative function of God is, like himself, eternal.
Also, Swami Vivekananda says the following in his complete works.
The Hindus have received their religion through revelation, the Vedas.
They hold that the Vedas are without beginning and without end. It may
sound ludicrous to this audience, how a book can be without beginning
or end. But by the Vedas no books are meant. They mean the accumulated
treasury of spiritual laws discovered by different persons in
different times. Just as the law of gravitation existed before its
discovery, and would exist if all humanity forgot it, so is it with
the laws that govern the spiritual world. The moral, ethical, and
spiritual relations between soul and soul and between individual
spirits and the Father of all spirits, were there before their
discovery, and would remain even if we forgot them.
The discoverers of these laws are called Rishis, and we honour them as
perfected beings. I am glad to tell thisaudience that some of the very
greatest of them were women. Here it may be said that these laws as
laws may be without end, but they must have had a beginning. The Vedas
teach us that creation is without beginning or end. Science is said to
have proved that the sum total of cosmic energy is always the same.
Then, if there was a time when nothing existed, where was all this
manifested energy? Some say it was in a potential form in God. In that
case God is sometimes potential and sometimes kinetic, which would
make Him mutable. Everything mutable is a compound, and everything
compound must undergo that change which is called destruction. So God
would die, which is absurd. Therefore there never was a time when
there was no creation.
So, Lord is eternal and as Supreme God is eternal, the process of creation, preservation and destruction is happening since eternity.
Adi Shankara says that process of Creation, Preservation and destruction is just an apparent manifestation, as discussed by Swami Vishwananda in this answer.
In normal time souls are born in animals for Bad Deeds but in the beginning on what basis were souls in animals were put ?
Atmans aquire bodies in this cycle of creation based on their respective karma of previous cycles. Since there is no first cycle of creation, you can apply this logic to all cycles.
For example, those who perform 100 Aswamedha Yajnas become Indra. So, a king or Kshatriya of previous cycle who performed 100 Aswamedha Yajnas in last Manvantara becomes Indra for first Manvantara of first kalpa in the present cycle.