I know formal languages are widely used in linguistics, especially for computational linguistics. However, I do not understand where this connection started - Wikipedia says that formal language theory sprung out of linguistics but I would like to find a good introduction that will help me see the connection once and for all.
I do not think there is a good "introduction", because you're referring to an era that preceding the modern trend of writing introductions.
The more-accessible "start" is Chomsky 1956 "Three models for the description of language" as well as 1959 "On certain formal properties of grammars". These works were not generally intelligible within linguistics, but the Chomsky hierarchy helped to define a fundamental research question – what kind of apparatus is required to formally describe human language? The hierarchy in particular caused linguists to focus on the concept of "power" / generative capacity. We knew that a system using only context-free rules is inherently superior to one using context-sensitive rules, and one using context-sensitive rules is superior to using unrestricted rewrite rules. Specifically, you can "do fewer things" with context-sensitive rules than you can with unrestricted rewrite rules, so unless unrestricted rewrite rules can be proven to be necessary, you should not embrace a theory with unrestricted rewrite rules, you should embrace a theory with context-sensitive rules. This consideration sort of fell by the wayside after about 15 years of generative grammar, when transformational rules fell out of fashion, but even to this day people talk about some theory being "too powerful", invoking the concepts of the Chomsky hierarchy (generally without any of the math).
The linguistic contributions to formal language theory seem to be fairly minimal.
My first introduction was Bob Wall's introductory book, and, though it is dated, I still recommend it. It is based on the Chomsky hierarchy of formal languages.
The focus skews toward phonology, but Jeff Heinz's notes on this are quite good IMO:
Also, with slightly less focus on formal language theory (but still some), but a lot of motivation for computational linguistics, are Ed Stabler's (now quite old, but still great, and VOLUMINOUS) notes: