Du hast alles etwas allgemein gehalten.
Was stört dich genau an dem 18-135 und was willst du damit fotografieren? Sind weitere Objektive geplant? usw.
Wenn es dir nur auf optische Güte ankommt, nimm Festbrennweiten, kommt es dir auf Güte an, nimm Limiteds (besser verarbeitet geht kaum).
Eine gute Mischung sind die 16/ 17 - 50mm f2,8 Objektive.
Generell ist die optische Qualität besser, je kleiner der Brennweitenbereich ist und in der Mitte jedes Brennweitenbereichs am besten.
Das Pentax (16-50) ist recht teuer und schwächelt offen etwas bei OB (allerdings durchweg besser, als das 18-135), in allem anderen (Bokeh, Kontrast, Farbdarstellung, Haptik, usw) ist es erstklassig für ein Zoom.
Das Sigma 17-50 ist günstiger und etwas Randschärfer bei OB, das Tamron am günstigsten, dafür gibts Nachteile im Bokeh, Haptik und Farbdarstellung.
Das Sigma 17-70 hat einen guten ruf, ich würde aber wegen der Lichtstärke zum 17-50 raten.
Wenn das nötige Geld da ist und Randschärfe dir nicht das wichtigste ist, nimm das Pentax 16-50 (am besten gebraucht mit neuem Motor (>01.2012 eingebaut))
EDIT:
Füll am besten mal den Fragebogen aus, dann lässt es sich deutlich besser beraten.
mMn. wirst du nur auf das falsche Pferd gesetzt haben, wenn du unrealistische Vorstellungen hast oder eine extrem hohe AF-C Geschwindigkeit brauchst.
Eine K3 braucht ein wenig Einarbeitung (da sind die EInsteigerkameras einfacher), ermöglicht dir aber auch einiges. Einfach Erfahrungen sammeln und es wird besser
Als Allroundobjektiv ist das 18-135 durchaus zu empfehlen. Klassisch bei solchen Superzooms ist die etwas schlechtere Qualität am Brennweitenende (hast du bei jedem Zoom.. mal mehr, mal weniger).
Generell auf >=f8 abgeblendet und im Mittleren Brennweitenbereich genutzt, bekommst du damit schon sehr gute Bilder hin. An den extremen Brennweiten würde ich darauf achten möglichst wenig wichtiges am Rand zu positionieren.
Ich würde dir raten erstmal mit dem 18-135 weiterzumachen und nach ein paar Monaten (wenn du dann noch unzufrieden bist) zu gucken, welche Brennweiten du am meisten genutzt hast.
Kennst du diese Sweet spots kannst du für dich viel besser entscheiden welchen Brennweitenbereich für ein Zoom du brauchst und / oder ob und welche FB Sinn für dich machen