It's not just the first build, the later ones are slow for me as well. Eclipse's first build (e.g. after you do a Clean project) is also slow but after that it's very fast.
are you using wildcards (eg. com.foo:bar:1.3.+) in you deps in gradle? it forces gradle to look to the internet every time you build (unless you've checked "Work Offline")
Actually using dynamic versions (i.e. 1.3.+) are cached for 24 hours (unless you override the default). So you typically just pay the penalty for looking for new versions once a day.