iMessage is designed to prefer sending a message over Apple's servers vs sending via the carrier's SMS system.
When you send a message, iMessage checks to see if the recipient is registered with Apple's Messages server. If the target you are messaging is not registered with Apple's Messages server (ie they use an Android phone), your iPhone will send the message via SMS.This uses the carrier's Voice protocols, not Data protocols. This is why you can send a text even without a data plan or with a 'dumb' phone.
When sending to a Registered Messages user, iMessages will send a message via Apple's Messages server. This requires a DATA connection. Apple assumes every iPhone has a Data connection, and since iMessages is designed to NOT use SMS (saving the user money), it will wait until it gets a data connection before sending the message. A Data connection is either EDGE/3G/4G from the carrier, or Wifi.
This is why you can send to a non-iPhone user right away, but an iPhone user does not get the message promptly.
Now, Apple didn't assume everyone pays for text messages, so in case they actually have a texting plan, and PREFER to send via SMS, there is a setting in iMessages that will send a message via SMS, if it fails to send via the preferred Data connection. While by default iMessages will not send Registered users via SMS, its easy to tell it to do so. Simply go into iMessages settings, and enable the 'Send via SMS" setting, and you will be able to send to other iPhone users.
Very long additional info:
Messages is really a combination of SMS + Instant Messaging services. For users of iDevices, it really is a great experience and how a message is delivered is seamless. However, if you use other devices, or if your device is not 'standard' in some way, Messages can be difficult to manage and understand.
Since Messages combines both SMS and IM, it allows Messages to be delivered via both methods. "IM" style messages are delivered via the Apple Message Server, while SMS messages are sent via the carrier service. Where it gets confusing is that even iDevices that have no carrier service at all, such as iPod Touch and some iPads, can send Messages.
The Confusion
If all devices had carrier services, this would be simple: if data service was available, Apple Messages service would send via data, and use SMS all other times. But since all devices do not have carrier services, it gets tricky: An iPhone can send a SMS to another device, and data-based Messages to any iDevice. Of course, it can't send a SMS to an iDevice that does not have carrier service. Likewise, an iDevice without carrier service can not send a SMS to an iDevice, nor any other device, but they can send a data-based Message to any iDevice. Here is a summary:
iPhone > iDevice: Messages (data) only
iPhone > iPhone: Messages and SMS
Android > iPhone: SMS only
iDevice > iPhone: Messages only
iPhone > Android: SMS only
iDevice > Android: not possible with Messages
Android > iDevice: not possible with Messages.
Where things get really confusing is when you have registered BOTH a telephone number on your iPhone, and an email address with the Apple Messages Server. If you have an iPhone, it will default to registering your phone number, allowing you to add an email address. an iDevice will allow only an email address, since it does not have a phone number.
For iDevice and iPhone uses, they do not notice or care which contact form was used to send the message: either will do. But in order to send to a non-iDevice, a user of an iPhone MUST send to a phone number (since it goes via SMS). But an iDevice can not send to a non-registered non-iDevice, such as an Android phone at all, since it does not have SMS capability. Nor can an Android phone send to an iDevice over SMS for the same reason.
Therefore, when there is a mix of iDevices, iPhones and Android phones, the user must carefully choose what contact form to use. For example, I have an Android phone, an iPad, and a Mac. I can send Messages to my wife's iPhone from my iPad, to either her phone number or email address, both of which are registered. But to send her a message from my Android, I can only use her phone number. When she contacts me however, she must think first: if she messages me at my email address, it will go to my iPad and Mac, but in order to reach my Android phone, she must choose my phone number. Since most people simply open existing conversations, this gets really confusing it they were conversing using a different contact form.
Your device problems:
I believe your issue is that your iPhone is 'non-standard' in that you do not have a carrier data plan. Therefore, it behaves much like an iDevice like an iPod Touch. Only if an iPod Touch has wifi will Messages work. But since you have SMS, you are able to send an SMS, and likely receive an SMS from non-iDevices. But if another iDevice sends to your registered email, it will fail, until you are on Wifi. I suspect this is true if you send to a registered iphone phone number too: Messages is going to try long and hard to send via data, so will wait until connected. You can force it to use SMS as discussed above.
So, carefully look to see what contact form your wife and you are using when you use Messages. If your wife is sending you Messages using your registered email address, they will not arrive on your phone till you get Wifi, whereas if she is sending to your phone number, you will likely get it right away. An Android will be able to text you immediately, since it is sending via SMS. I suggest that you both use the phone number only (and set her phone to send via SMS). You can register to receive Messages sent to a registered phone number via your Mac Messages as well, so that you can receive Messages sent to the iPhone via both iPhone and Mac.
Best Answer
The messages app on the Mac has it's own preferences. Check if you're iMessage account is set up there and has a password set – perhaps you deleted it through keychain. If that doesn't help remove it with the minus and re-add the account.