Long-running operation to update an Android appwidget

but much to my surprise it appears that onHandleIntent() is single threaded

Yes.

if i have two widgets, and then both update and start the intent service, they update sequentially ...

Yes.

but i'm just wondering about a best practice for this type of pattern.

Your IntentService was a fine upstanding solution, IMHO. Remember that Android runs on slow CPUs, with devices with little RAM. Running lots of threads in parallel is generally not a good idea.

then i'm getting into starting a thread in onHandleIntent(), which requires a wake lock, and it just seems it's getting all too complicated.

Try my WakefulIntentService.