This is kind of a tough choice. First of all, we'll assume that the ~15 year old PSR-E413 that you are considering is completely functional. Beyond that, there are some similarities, and some differences. And many are really based on personal preference, based on how the keyboard will be used. Now, keep in mind that I am basing what I am posting here on data from Yamaha's website for the E373, and a Google search for specs on the E413, as I have no direct experience with either keyboard, except for playing the E373 briefly in a music store.
You mentioned recording. The edge here would go to the E413, as it has a built-in 5 track sequencer, with a sixth track available for backing drums or style accompaniment. The E373 only has a two track recorder. This means you can "lay down tracks" and record more complex multi-tracked compositions on the E413 without using an external digital audio workstation (DAW). But of course, if you use a DAW on a computer, combined with an audio interface that converts the headphone audio sound into USB digital data for your computer, then you can do as much multi-track recording as you want, with any keyboard, directly on the computer -- with the complexity of the recording only limited by the capabilities of the computer. But it can be helpful to at least start recordings directly on the keyboard, and having more recording capability on the keyboard, which the E413 has, can be helpful.
The next thing to consider is registrations -- these are user-assignable presets that store most of the settings of the keyboard, such as any sounds you've set up, any changes to those sounds (such as reverb, chorus, or effects), and split and layering of the sounds on the keyboard, and any style selected. These registrations allow you to quickly change the sound and characteristics of the keyboard while you're a playing a song, allowing you to easily change sounds when going from, say, a verse to a chorus, or a chorus to a bridge, for example, and are most helpful during playing songs "live", as opposed to recording songs. Honestly, both of these keyboards are lacking in this department. The E413 has 16 registrations -- eight banks of just 2 registrations each. This means that, while playing a song, you can have a bank selected and easily go back and forth between two registrations with a push of one button -- but that does not allow much flexibility. If you want to access any of the other registrations during the song, you have to select another bank first, then select one of the two registrations of the new bank -- requiring multiple button-presses, which could be cumbersome during live playing of a song.
The E373 has only 9 registrations, and you access them by hitting a "Registration" button, then pressing the numbers 1 through 9 on the numeric keypad. I am not sure if you have to hit the "Registration" button each time you want to change a registration, or if you can just hit it once, and just use the numeric buttons for the registrations from that point on, and only need to hit the "Registration" button again if you use the numeric buttons for something else in the mean time, such as style select or voice select. Perhaps someone with an E373 could weigh in here. But in any case, 9 registrations is still not a whole lot if a person starts learning a variety of songs and wants to easily change between a wide selection of sounds (such as rock sounds, Classical sounds, orchestral sounds, jazz sounds, etc.) while playing.
Next, there is sound customization. Both keyboards have specific strong and weak points here. The E413 has a mini-synthesizer function on board, where you can take any sound and alter the filter and envelope (attack and release) settings, like on an analog synthesizer, and come up with cool new sounds. You can then save these sounds in a registration. Also note that some of these functions can be assigned to knobs that are on the left side of the E413, which allows the player to alter the sound during a live performance -- again, in a similar manner to how this can be done on an analog synthesizer. Assigning the filter to the knobs, in particular, can give the player a wide range of sound effects and control while playing. The E373 does not have such features, but instead, it offers a full set of digital effects, like phase shifter, Leslie-type rotary speaker, and a few dozen other effects, which are also great for customizing the sound, and again, these modifications can be saved to a registration. Beyond the filter and envelope, the E413 can only add basic reverb and chorusing.
Beyond on-board recording, registrations, and sound customization, I would say that the E373 excels in most other areas, and of course, this would be expected as it is a much newer model. It has more onboard sounds and registrations (though not dramatically more). More polyphony (48 notes maximum versus 32 notes maximum). And S.Art.Lite which allows for some "on-the-fly" expressive changes to certain sounds while playing (though it should be noted that the E373 does not have a pitch-bend wheel, which can be a drawback). It can even output stereo digital audio -- presumably to a computer.
But here is a very important consideration for both keyboards: Neither one has a USB-to-device port, as far as I know. For sure, the E373 doesn't have it, as I do not see it on the pictures of the keyboard on Yamaha's website, and I'm pretty sure the E413 doesn't have it -- I don't think Yamaha started including it on the E-series keyboards until the PSR-E433, which came out in 2012, and even from that point on, only on the E400 series (E433 to the current E473). A USB-to-device port allows you to simply put a thumb-drive/flash-drive into the port and easily back up and retrieve the data on the keyboard. Without this port, the only way to save data is to hook up the keyboard to a computer.
Other than easily backing up data, a USB-to-device port also expands the capabilities for live playing. For example, on the E433 (which I have), there are 32 registrations (8 banks of 4 registrations each) -- this is much better than what is on the E413 and E373, but still a little light. If I wanted to have access to more registrations during a performance, I could have them on backup files on a flash-drive plugged into the keyboard and access them between songs (loading data from the flash-drive would not be possible during the middle of playing a song). And no computer would be needed.
So, in conclusion, I would say...
Between the E413 and E373, for live playing and multi-track recording, the E413 has a slight edge. As for sound customization, it's kind of a wash, with the E413 having the synthesizer type functions, and the E373 instead having the digital effects. But the E373 is pretty much superior in most other respects, with things like number of sounds, number of styles, polyphony, and S.Art.Lite.
Again, remember that neither keyboard has the USB-to-device port, so you may also want to consider a newer PSR-E400 series keyboard -- a PSR-E433 or newer (E433, E443, E453, E463, or the latest model, the E473), if you can find one and it's in your budget. Other than the USB-to-device port, you get 8 banks of 4 registrations with all of these models -- which is much better for live playing. The E453 and E463 also add digital effects (though not as many as on the E373) so that you can get this feature along with the synthesizer type functions. The E463 and E473 have sound sampling functions. And the E473 also includes the S.Art.Lite function found on the E373, as well as a full complement of digital effects -- making the E473 pretty much the most versatile choice -- but of course, also the most expensive!
Sorry for the long post, but hope it helps! Feel free to ask any questions.