You are correct on the different headers (a.k.a. banners), and that plain SSH will not traverse an HTTP proxy. But proxies come with inbuilt traversal methods, and an HTTP proxy come with the HTTP CONNECT word. Since you are not sure whether is is an HTTP proxy or not I'll also add info about SOCKS proxies.
There are pretty much only 2 types of proxies out there: HTTP or SOCKS (other proxies are often just hacks put together). 3128 is a (more-or-less) standard port for the squid proxy, therefore it is highly likely that is the software being used to create the proxy. And squid can run either HTTP or SOCKS proxies.
Both Firefox and Chrome have setting to use the proxy as an HTTP proxy or a SOCKS proxy. It is written next to the option where you input the address of the proxy. If both work, then squid is configured to accept both.
Either way, SSH can be configured using ProxyCommand to use that command to traverse a proxy. But you still need a command that will be capable of traversing the proxy itself. There are several options out there, my favourite is ncat (the netcat program provided with NMAP) and I'll use it in the example below but I'll add more options at the end of the answer.
Inside your ~/.ssh/config you can add
ProxyCommand /usr/bin/ncat --proxy-type http --proxy 172.18.10.1:3128 %h %p
Where --proxy-type can also be socks4 or socks5. SSH will use that command to traverse the proxy and then establish the connection.
Other options
Plain nc can also be used, as follows:
ProxyCommand /usr/bin/ncat -X connect -x 172.18.10.1:3128 %h %p
And for SOCKS the -X arguments should be "4" (SOCKSv4) or "5" (SOCKSv5). Unfortunately, nc varies from platform to platform and some options may not be available.
If you still have a firewall after the proxy see Gilles's answer on unix.SE for an extra bag of tricks.
Extra note
You can disable HTTP CONNECT in squid. And if that is disabled all bets are off, since the proxy will not allow any traffic that is not a valid HTTP WORD (that is not disabled, e.g. GET, POST) from traversing it.
Yet, the big problem with disabling HTTP CONNECT is that then HTTPS traffic cannot traverse the proxy, therefore it is unlikely that an HTTP proxy has HTTP CONNECT disabled.
Update: Can't a proxy simply allow "native" HTTPS to pass through?
This is a question in the comment by @Pacerier which I found may be interesting to address. Full question:
Can't a firewall allow native HTTPS while blocking HTTP CONNECT HTTPS?
Which I will mangle into (since we are talking about proxies really):
Can't a proxy allow native HTTPS connections while blocking HTTP CONNECT HTTPS?
Yes and no. First, a proxy do not block connections that do not go through the proxy, it only decides on connections that go directly to the proxy. In theory a proxy could allow "native" HTTPS to go through, the problem is that "native" HTTPS is basically any stream of bytes since it is encrypted at TCP level. In other words, HTTPS is not a protocol that is visible by looking at the packets, that is by design.
The counter argument to that would be that a proxy would be capable of checking whether a stream performs the HTTPS handshake at the beginning and, if both sides "complete" the handshake then allow any stream of bytes to continue going through this connections. Note that one cannot know whether the connecting parties succeeded in the handshake, that is also by design, therefore a proxy can only know that a handshake was sent or not.
Assuming the above, you can now use your proxy for any protocol since you can simply fake an HTTPS handshake and then send whatever you want. This defeats the purpose of most proxies, i.e. you turned your OSI layer 7 (HTTP) proxy into an OSI layer 4 (TCP) proxy. And on a layer 4 proxy it does not matter anymore whether you are using HTTP, HTTPS, FTP or LDAP.
References (not very related but I took some info from there)
