I hate to say it, but powering up pokemon before level 15 or so is probably inefficient. Certainly not the end of the world though, and it did let me take on some weaker gyms solo at level 13. Burned through a lot of potions and revives, but I was throwing potions away for space. Wasn't really "worth it", XP-wise, and I only got a handful of dimes worth of credit... But it was fun though.
With careful dodging and spending items I was taking on 1000-12000 mons with 500-600 mons. Keeping in mind that you get 6, and many gyms will just have 1-3, and you only need to defeat 1 to de-level the gym a little. And you can get a dime by taking a gym then immediately cashing in for the day, if you (like me) aren't likely to hold several at once.
Also, and coming from Ingress I found this amazing, *you can team up against a gym*. Your friend even shows up on the battlescape! The defender doesn't have to split its attacks (each attack targets all attacking pokemon), so it's actually not as advantageous as it sounds, but it goes a *lot* faster which is helpful.
So I don't regret powering up my favorite pokemon really, it was worth it just to experience gyms. But the more effective thing is to power level yourself. That means capturing lots of pokemon and hatching eggs. Then when you can't hold back, pop a lucky egg for 30 minutes of double XP, then do as many evolutions as you can. (I did so while walking with incense, with three eggs about to hatch, just to make best use of my precious lucky egg. I haven't seen one drop from a stop, just leveling and the store).
Sad note: You don't get any bonus experience for unlocking a new pokedex entry via evolution. Apparently you have to find a wild one to get the bonus :/ It's just the same 500XP as evolving a pidgey, though, so meh. The crappy thing about that is there's not much reason to do the expensive tier 3 evolutions, though. It makes more sense to make a bunch of metapods than to hold out for a butterfree.
Butterfree and beedrill aren't even especially good, that I can tell. Whereas vaporeons are deadly as heck for being so easy to acquire. The gyms up here are fricken full of vaporeon, gyrados, sometimes flareons. Only slightly exaggerating. And oddly I have better luck taking on the vaporeons with my own, than I do with my jolteon...
Level is kinda everything. It determines how much you can power up a pokemon, but also makes powering-up obsolete by letting you find better ones for free, and unlocks the good potions and balls (which drop from pokestops quite commonly).
I'm not worried about the pokemon getting harder to capture, though. Farming strong balls and berries in Go is SO EASY compared to Ingress. In Ingress, harvesting a location 5 times would make it "burn out" for several hours. Rare items would increase this limit. Yes, we spent rare items in order to keep farming a high-level portal for over half an hour, because 3 (ideally
max-level people had to capture and hold it for it to be worth farming. Whereas in Go you can literally park next to three portals all day long. Not that it'll take all day, at ~18 items every 5 minutes. (I prefer to walk along a circuit though. More efficient, incubates eggs, more fun)
tldr: back in my day we had to farm uphill both ways
Also I'm only (just recently) level 17 so meh, but my dad's 19 and it isn't that much tougher to capture on his phone (he was driving).