My front wheel was pretty out of true. It's a VERY cheap wheel - a formula hub laced to an Alex DA14 rim. Pattern is 3-cross. And there's 36 spokes.

It was so out of true that there was a noticeable shudder/pulsing at the brake lever when braking. However, in about 15 minutes, I got it relatively true and the brake shudder was gone. I even rode straight off a curb to test my truing job, and I'm 185+ pounds (not counting gear). The wheel was still as true as it was when I got home.

So I felt pretty good about myself. At this point I took a 20 spoke, radically laced front wheel out of my closet. It wasn't that much out of true, but I wanted to perfect it. I noticed that I couldn't really get anything to change without twisting the spoke wrench way way more than I was comfortable with. On the 36 spoked wheel I noticed that little quarter turns and half turns got me where I wanted to be; on this one, it seemed like quarter and half turns did absolutely nothing.

I am going to take this wheel to the shop to get it trued. In the meantime, are radially spoked wheels really harder to true than cross-spoked wheels? Or does it just have to do the number of spokes?

It's probably spoke windup.

Given market demands for low weight. more expensive wheels tend to have lighter spokes and alloy nipples which stick when not properly lubricated.

Contemporary rims tend to be deeper allowing higher tension. Lower spoke counts also call for higher tension. This increases windup.

Using anti-seize on the spoke threads at 120-130kgf you can get 1/4 turn of windup in a 2.0/1.5mm butted spoke before tension changes, and with problems even a half turn may not be enough.

Add a drop of oil on the hub side of each nipple and socket to reduce friction. You'll get less windup, it'll be more comfortable, and you won't bend aluminum nipples that aren't too frozen.

Put a tape flag on a representative spoke (I like the first (and second for rear wheels) after the valve hole) or Sharpie dots all around to see what's happening with windup. Measure your quarter or half turn from where the windup stops and completely undo it.

Ah, I think you nailed it. These 20 spoked wheels have 30mm deep aluminum rims.

Do you think I might have done any permanent damage by screwing around with the nipples without giving a thought to lubrication?

I am definitely going to try the Sharpie method as well ....

You're fine as long as the nipples don't look twisted or trapezoidal not square. If they turned freely problems are unlikely provided you seated the spoke wrench all the way and weren't just twisting the end of the nipple.

Okay, I just looked, and all the nipples look fine. I did use a cheap spoke wrench and I think it may have been slightly oversized as it slipped off some nipples.