Is public-key cryptography the only option in this scenario?
"Is to be encrypted" is not a ultimate goal. You do not encrypt data for the sake of it; you encrypt data as a way to ensure a given security property, e.g. transmitting some data between two machines, without compromising the data confidentiality with regards to attackers who may spy on the transmission line (or even alter data in transit).

If:


your problem is indeed a question of data transmission;
you can arrange for both sender and receiver to share a common password;
the transmission uses an online protocol where messages can flow in both directions;


then you can use a secured data tunnel, with a Password-Authenticated Key Exchange protocol to establish a shared symmetric key (used for tunnel encryption and integrity) with mutual authentication relative to the password. PAKE protocols ensure that attackers spying on the line, and even active attackers who can try to impersonate the client or the server, learn nothing which can be used to "guess passwords". With a PAKE protocol, each "password guess" must imply some communication with an honest system (the real server or client). Server and clients can then easily detect brute-forcing attacks after only a few dozen tries. Therefore, PAKE protocols are secure even with passwords of low entropy.

A secure tunnel with a PAKE protocol is a complex beast, easy to get wrong in many ways. Hence you really should rely on an existing, well-analyzed protocol. I suggest SSL/TLS with SRP; this is supported by at least the opensource GnuTLS library.

If the transmission is offline (e.g. in an emailing context: the sender must send all its data in one go, and that must be sufficient for the receiver who acts only afterwards), then a password will not be enough, although you can make it quite hard for the attacker by using an appropriate key derivation process, in which the password is hashed many times with a random salt. Usual recommendations are PBKDF2 and bcrypt. A password with about 30 bits of entropy is sufficient if you use a key derivation process which implies at least a few seconds of computation on a reasonably recent PC.

To get more security than that, you must use a stronger shared secret key; if this implies an unsolvable key distribution process, then you can go to a public-key based scheme, the archetypal protocol being OpenPGP (see GnuPG for an opensource implementation). You still need to make sure that the sender has the genuine receiver's public key, but (at least) this implies no sharing of secret data.



Edit: with the new phrasing of the question, the answer is now clear: PAKE. You want to get a shared secret with mutual password-based authentication, and resilience against offline dictionary attacks. PAKE protocols are precisely designed for that. All currently known PAKE protocols involve some "public-key-like" elements, so you will not avoid at least some mathematics. SRP is an adequate, well-documented PAKE protocol.