Lo que comenta tu jefe de enlazar es algo reconocido por todos los SEOs, tienes que conseguir enlaces que sean naturales o en caso contrario que lo parezcan. Si creas una red de intereses entre varias webs es más que porbable que Google lo detecte y deje de valorar esos enlaces.
Lo que pasa es que Google usa ese filtro para evitar los enlaces "antinaturales", que es lo estás haciendo al intercambiar, pero a veces son mejores esos enlaces "antinaturales" que los reales. Los mejores enlaces con diferencia que tengo en la web de la firma es desde otro sitio mío de temática parecida. Uso la misma cuenta de Adsense, Analytics, etc. Estoy seguro que sabe que ambos dominios comparten dueño pero la temática es más importante que eso... claro y que al ser mío enlazo en el mejor sitio posible. Si tienes 5 blogs y todos enlazan a la web principal es sospechoso, pero que en uno de ellos (el que tenga más relevancia) enlace seguro que sería positivo. Pero si han dicho que no lo hagas, no vayas a hacerlo. Ya sabes, el jefe siempre tiene razón y en caso de no tenerla volver al punto primero.
Para ganar relevancia en tus blogs deberías escribir un poco distinto. Son blogs muy útiles a nivel SEO pero poco atractivos, demasiado indefinidos. Tienes que escribir dando más opiniones personales, "tal ciudad es muy bonita y estos son sus atractivos..." es algo que existe en muchas páginas, tienes que dar alguna información personal (un sitio menos conocido, algo que te guste... un hostalito, sitio para comer, las vista que hay, un descuento) da igual que sea de primera mano o comentario de un conocido o también una forma de escribir más o menos desenfadada, algo que destaque. Orientar los escritos a un público potencial, turistas de hotel, mochileros... depende de a quién escribes resaltarás una u otra cosa.