Should I embed a related work section in the introduction, and how would I do this?
The structure of your paper should make it attractive to read and easier to understand. So keeping to the common structure in your field is usually helpful, but not a dogma that should be obeyed when it's not useful.

Introduction -> Related Work -> Main Contributions is a pretty common start for CS writing, so making it a separate section would be the default option.

However, if you have to lean heavily on a literature discussion to motivate the need for your work, it can make more sense to pull them together into a single chapter, perhaps with subsections.