I don't have any experience with OpenBSD but i can tell you that you are on to something in regards to the terminal type.
Screen and xterm types are probably not the right ones to chose though (i guess you know that). OpenBSD's console likely has it's own type (pccon maybe?) but something simple like vt100 might also (more or less) work. In general i'd feel pretty strange about having to supply the right TERM setting by hand though (i'd expect login, the shell or at least .profile to set a correct value).
There might also be some relation to the console font but unless you set something special there i would not expect it to be the root of the problem as the default font probably is capable of drawing boxes.
Another possible cause could be a broken/incomplete termcap/terminfo (not sure what OpenBSD is using) database but again as long as you didn't mess with it i don't see a reason why it would be bad.
Edit: I guess you solved the mystery yourself. I very much didn't expect anything to still not support UTF8 in 2023.