how difficult/easy would it be to insert/overlay one video into another, akin to picture-in-picture (PIP) in the top left corner, for example...?

Should be fairly easy.  I would get a popular free video editor and look for a tutorial.

Something like Lightworks


Pip tutorial

In something like Adobe After Effects it's easy. Start a new comp, drag the big or bottom clip to the timeline, drag the smaller clip on top. Scale down the top clip and move it to where you want it, then render. Depending on the clip sizes, resolution etc etc rendering would take more time than the actual "work".

If someone had Adobe After Effects I do not think that they would be asking about video overlay.  I have not used a consumer video editing program in about 10 years, but I would think that most would have the ability to do it.  I know that this thread is kind of old but if you have not already done it and still need some help please post up, or send me a PM.  I work in Video Production full time and will help if I can.

Phil

If you have AE, good chance you have Premiere and don't need to do anything other than import, resize, and transform.