Well, probably a text file or something. Re-encoded videos will make the patch ridiculously huge, and at this time I really have no idea how to insert softsubs.
We'll probably do ToR after this as well, it shouldn't be hard to port our stuff to it.
ToD PS2 is also a possibility if it doesn't make it over. I'm expecting it to be based on the ToD2 engine, like ToR is. But we'll see when it comes out.
So, when is a menu patch coming? What's the best range?