the classical す is only applicable to nouns, and certain ones at that, got it. So even if a verb has す, it's not the old form of する unless it's attached to a noun.
You got it right.
Speaking of the noun forms, (I could probably figure this out on my own if I think about it but) are most verb stems able to be nouns in that way? Or is there a rule to know when it's likely to be "noun-able", if most aren't?
It depends on the verb. Some are commonly used as a noun (e.g. はなし from 話す, はたらき from 働く), and some are not used as a noun solely. For example, 見（み） from 見る is not used as a noun by itself, but 花見 "cherry‐blossom viewing" or 月見 "moon viewing" are common words. 食べ is rarely used even in compound words, because there also is another verb 食う（くう）as the same meaning "to eat", and its 連用形 食い（くい/ぐい） is more commonly used as a noun (e.g., 早食い（はやぐい）, 大食い（おおぐい）).
I'm also wondering about something interesting I uncovered; one of my Japanese friends recently used a strange version of 「食べる」 which was 「食す」(しょくす I guess), and when I asked him about the difference, he basically said it's 丁寧語.
食す (yes, the reading is しょくす) and the modern version 食する are
not the 丁寧形/polite form of 食べる. They are different verbs of the same meaning. In fact, there are polite forms for each verb, 食します and 食べます, respectively.
食す/食する is more formal, stiff or written-language-like than 食べる. This is because it's originally used in 漢文 (a method to read classical Chinese texts as Japanese sentences), and Chinese was the formal language used in official documents, just like Latin in Europe. (Some educated people wrote their diaries in Chinese, or Chinese-like Japanese.)
The same difference exists also in some verb pairs, for example 書する（しょする） - 書く（かく） or 要する（ようする） - 要る（いる）. As you might already realize, しょく, しょ and よう are 音読み "Chinese-origin reading", and た（べる）, か（く） and い（る） are 訓読み "Japanese-origin reading". (Incidentally, 読み "reading" is also from the 連用形 of 読む "to read" in 音読み and 訓読み.)
By the way, I'll use this as one of my own test questions for myself: Is this a classical する verb? I think the answer is no, because the noun form must be 「食べ」, not 「食」.
As I wrote above, 食す is the classical form of 食する. 食 is actually a noun (e.g. 食が細い). However, the conjugation type is not completely the same as -suru verbs.
negative
食さない (食しない is not wrong, but almost obsolete.)
食さず（食せず is usually interpreted as the negative potential form, but can be used as the negative form in very classical texts.)
potential
食せる (not 食できる)
This is a trivial thing, but this phenomenon is called サ変動詞の五段化 "changing of the conjugation type of -suru irregular verbs to the godan conjugation type" in Japanese grammar. It only occurs on single kanji stem -suru verbs, and doesn't occur on 勉強する, 掃除する or 行動する in my previous examples. Also, it differs depending on the verb in what degree the verb is changed, i.e., which type, for example 〇しない or 〇さない, is more commonly used.
examples (quoted from a research with using Asahi Newspaper database)
愛す/愛する
negative
〇愛さない
×愛しない
〇愛さず
×愛せず (This form exists, but it's only used as the negative potential form.)
potential
〇愛せる
×愛できる
imperative
〇愛せ
×愛しろ
屈す（くっす）/屈する（くっする）
negative
×屈さない
〇屈しない
×屈さず
〇屈せず
potential
×屈せる
×屈できる
(The potential form is hardly used in the first place since 屈す/屈する is a non-volitional verb.)
imperative
×屈せ
〇屈しろ
Thus, it can be said that 愛す/愛する is closer to godan verbs, and 屈す/屈する is still a -suru verb.
so essentially the 当たらぬ part of 「当たらぬ宝くじ」 is like the adjective in a sense (even though it doesn't have い or な) so to make any kind of noun phrase with a verb + ぬ it would generally be like how adjectives are in Japanese, where it has to come before the thing that it's modifying?
That's right.
And then using は after a noun, then a verb with ぬ after は just makes the statement about what state the noun is in?
It's more simple. Basically, when a verb (or adjective or copula) is put at the end, it's a sentence. Thus, 宝くじは当たらぬ。 is just a classical version of 宝くじは当たらない。, and needless to say, 当たらぬ宝くじ is the classical version of 当たらない宝くじ, as well.
The same goes with the affirmative form of verbs, past form, potential form, etc..
当たる宝くじ(noun)
宝くじが当たった。 (sentence)