Initial Connection to Bitcoin If this is the first connection of a new client to the network, I would like to know after the exchange of version &amp; verack messages from both peers, which message is exchanged. I guess every time a getblocks message is needed because our client needs to check if the blockchain we have is the latest. So the getaddr messages follow the getblocks message? 

And if the client had connected in the past will he need any getaddr messages or his database of peers would be enough?
I guess every time a getblocks message is needed because our client
  needs to check if the blockchain we have is the latest.


Thats right. You can also compare the blockheight from the version message, but you will still need to check if you are not on a fork. 


  So the getaddr messages follow the getblocks message


I would say that up to you. If you connect to a new peer, and the chains are different, you dont know directly if he is on the wrong chain or you are. So it would be good to know some other peers to ask as well.
I think its better when you first call the getaddr message, because thats a one time command you run. If you ask for blocks, seeing you dont got all, you will start calling the getdata message and so on. Than your getaddr message would continuous be delayed.


  And if the client had connected in the past will he need any getaddr
  messages or his database of peers would be enough?


The stored peers should be enough. Remember, once a node is connected to a peer node, they share new peers by exchanging addr messages whenever a new peer is discovered. So you also get new peers without asking for them.
You will just have one problem, those peers which have disconnected. So its always a good idea to ask again for peers, just to be up to date.