広告IDを取得する場合、dependenciesには、play-services-base を設定する。

build.grade(Module: app)の例：※バージョンは、環境に合わせて変更して下さい。
dependencies {
	compile fileTree(include: ['*.jar'], dir: 'libs')
	compile 'com.google.android.gms:play-services-base:9.4.0'
}

AdvertisingIdClient.getAdvertisingIdInfo()に必要な機能は、play-services-baseに入っています。
(play-services-adsの依存関係の設定に、baseが入っています。)

(他の機能が不要な場合は) play-services-adsを指定しない。

失敗例：
compile 'com.google.android.gms:play-services-ads:9.4.0'

dependenciesにplay-services-adsを指定すると、
Project Structure/ Developper Services/ Adsの
「AdMob」欄にチェックが自動的に入ります。
(AndroidStudio 2.2で確認しました。バージョンによって挙動が異なるかもしれません。)

この欄にチェックが入っている場合は、デベロッパーコンソールの、
価格と販売/配布地域の、「広告を含む」欄に、

アプリに広告SDKが見つかりました
有効なAPKに広告SDKが見つかりました：
バージョン：～、SDK:AdMob
というメッセージが表示されます。(これも最近の変更かもしれません。)

最近、デベロッパーコンソールを開いてないという方は、一度確認してみるとよいかも？

補足

Project StructureのUIでAdMobのチェックを外すと、play-services-adsのdependenciesが削られますが、base等は新たに設定してくれないので、そのままだとエラーになります。要注意。

蛇足

広告IDを取得しようとすると、毎回、IOException(timeout)をthrowするよ～という場合は、デバイスを再起動してみましょう。
この現象は、Google Play開発者サービスが呼び出すサービスが止まってしまった場合などに発生します。

お約束の
変な自動設定を増やすのはやめよう・・(特に、見ていない場所の。)